\documentclass{ctexart}
\usepackage{ctex}
\usepackage{cite}
\usepackage{float}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage[colorlinks,linkcolor=blue]{hyperref}
\usepackage{geometry}
\usepackage{hyperref}
\usepackage{amsfonts, amssymb}
\usepackage{url}
\usepackage{array}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{fontspec}

\setmonofont{Consolas}
\linespread{1.5}
\pagestyle{plain}
\geometry{a4paper, scale=0.9}

\ctexset{
    section={
		format+ = \zihao{-3} \heiti \raggedright,
		name = {,、},
		number = \chinese{section},
		beforeskip = 1.0ex plus 0.2ex minus .2ex,
		afterskip = 1.0ex plus 0.2ex minus .2ex,
		aftername = \hspace{0pt}
    },
    % subsection={
	% 	format+ = \zihao{4} \kaishu \raggedright,
	% 	number = \chinese{subsection},
	% 	name = {（,）},
	% 	beforeskip = 1.0ex plus 0.2ex minus .2ex,
	% 	afterskip = 1.0ex plus 0.2ex minus .2ex,
	% 	aftername = \hspace{0pt}
	% },
	% subsubsection={
	% 	format+ = \zihao{-4} \fangsong \centering,
	% 	number = \ttfamily\arabic{subsubsection},
	% 	name = {,.},
	% 	beforeskip = 1.0ex plus 0.2ex minus .2ex,
	% 	afterskip = 1.0ex plus 0.2ex minus .2ex,
	% 	aftername = \hspace{0pt}
	% }
}

\lstset{
    basicstyle          =   \sffamily,           % 基本代码风格
    keywordstyle        =   \bfseries,           % 关键字风格
    commentstyle        =   \rmfamily\itshape,   % 注释的风格，斜体
    stringstyle         =   \ttfamily,           % 字符串风格
    flexiblecolumns,                             % 别问为什么，加上这个
    numbers             =   left,                % 行号的位置在左边
    showspaces          =   false,               % 是否显示空格，显示了有点乱，所以不现实了
    numberstyle         =   \zihao{-5}\ttfamily, % 行号的样式，小五号，tt等宽字体
    showstringspaces    =   false,
    captionpos          =   t,                   % 这段代码的名字所呈现的位置，t指的是top上面
    frame               =   lrtb,                % 显示边框
    language            =   [ANSI]{C},
    breaklines          =   true,
}

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{ %
        backgroundcolor=\color{white},   % choose the background color
        basicstyle=\footnotesize\ttfamily,        % size of fonts used for the code
        columns=fullflexible,
        breaklines=true,                 % automatic line breaking only at whitespace
        captionpos=b,                    % sets the caption-position to bottom
        tabsize=4,
        commentstyle=\color{mygreen},    % comment style
        escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
        keywordstyle=\color{blue},       % keyword style
        stringstyle=\color{mymauve}\ttfamily,     % string literal style
        frame=single,
        rulesepcolor=\color{red!20!green!20!blue!20},
        % identifierstyle=\color{red},
        backgroundcolor=\color[RGB]{245,245,244},
        numberstyle=\color[RGB]{0,192,192},
        stringstyle=\rmfamily\slshape\color[RGB]{128,0,0},
        identifierstyle=\bf,
        language=C++,
}

\title{\huge \textbf{《刷题纪实，for实习、秋招》\\ 史煜鑫}}
\date{}

\begin{document}

    \begin{figure}
        \centering
        \vspace*{8\baselineskip}
        \includegraphics[scale=0.4]{Figures/封面2.png}
        \vspace*{4\baselineskip}
    \end{figure}
    
    \maketitle

    \begin{table}[htb]
        \LARGE
        \renewcommand\arraystretch{1.5}
        \begin{center}
            \begin{tabular}{ccc}
                最后编译日期： & \today \\ \cline{2-2}
            \end{tabular}
        \end{center}
    \end{table}

    \begin{center}
        本文档使用 \LaTeX{} 编写
    \end{center}

    \clearpage

    本文档，涵盖了本人，在准备2024届实习、秋招的过程中，做进行的刷题的准备工作，同时，也包含了一部分，对于C++语言的复习，和一些C++的知识点。

    \tableofcontents

    \clearpage
    \section{算法一刷·代码随想录}

    参考资料，网站，代码随想录\cite{dmsxl}。

    \subsection{整数域上的二分}

    这里以《算法竞赛进阶指南》\cite{li_yu_dong}为准；

    本书使用的二分写法，保证答案始终处于闭区间 $ [l, r] $ 内，循环以 $ l = r $ 结束，每次二分的中间值都会归属左半段或者右半段之一。

    在\textbf{单调递增序列} $ a $ 中，查找 $ \ge x $ 的整数中最小的一个，即 $ x $ 或者 $ x $ 的后继。

    \begin{lstlisting}[language=C++, lineskip=3pt]
while (left < right)
{
    int mid = (left + right) >> 1;

    if (a[mid] >= x) right = mid;
    else left = mid + 1;
}
    \end{lstlisting}

    在上面的代码中，如果满足 $ a[mid] \ge x $ 的条件，则根据序列 $ a $ 的单调性，$ mid $ 之后的数字会更大，所以 $ \ge x $ 的最小的整数不可能在 $ mid $ 之后，可行区间应该缩小为左半段；同时，因为 $ a[mid] $ 也可能是答案，所以取 $ right = mid $ ；同理，如果 $ a[mid] < x $ ，根据序列的单调性， $ mid $ 之前的整数只会更小，所以 $ \ge x $ 的数字不可能在 $ mid $ 之前，可行区间缩小为右半段，且 $ a[mid] $ 不可能是答案，所以取 $ left = mid + 1 $ 。

    在\textbf{单调递增序列} $ a $ 中，查找 $ \le x $ 的整数中最大的一个，即 $ x $ 或者 $ x $ 的前驱。

    \begin{lstlisting}[language=C++, lineskip=3pt]
while (left < right)
{
    int mid = (left + right + 1) >> 1;

    if (a[mid] <= x) left = mid;
    else right = mid - 1;
}
    \end{lstlisting}

    在上面的代码中，如果满足 $ a[mid] \le x $ 的条件，则根据序列 $ a $ 的单调性，$ mid $ 之前的整数只会更小，所以 $ \le x $ 的最大的整数不可能在 $ mid $ 之前，可行区间缩小为右半段，同时，因为 $ mid $ 也有可能是答案，所以取 $ left = mid $ ；同理，如果 $ a[mid] > x $ ，则根据序列 $ a $ 的单调性， $ mid $ 之后的数字只会更大，所以 $ \le x $ 的最大的整数不可能在 $ mid $ 之后，可行区间应该缩小为左半段，同时，因为 $ mid $ 不可能是答案，所以取 $ right = mid - 1 $ 。

    上面两种 $ mid $ 的取法和缩小范围的方法是配套的，否则会造成死循环（可以手动推演一下）。

    上述两种二分写法，终止条件都是 $ left == right $ ，第一种中 $ mid = (left + right) / 2 $ ，所以 $ mid $ 不可能等于 $ right $ ，第二种中， $ mid = (left + right + 1) / 2 $ 所以 $ mid $ 不可能等于 $ left $ ，可以利用这一个性质处理问题无解的情况，即，在第一种写法中，将初始区间从 $ [1, n] $ 扩展为 $ [1, n + 1] $ ，如果最终的答案越界到了 $ n + 1 $ ，则说明原问题无解，同理，在第二种写法中，将初始区间从 $ [1, n] $ 扩展到 $ [0, n] $ ，如果最终的答案越界到了 $ 0 $ ，则说明原问题无解。

    本书中使用的这种二分方法的优点是始终保持答案位于二分区间内，二分结束条件对应的值恰好在答案所处的位置，还可以很自然地处理无解的情况，形式优美，唯一的缺点是由两种形式共同组成，需要认真考虑实际问题决定选择的形式。

    -

    -

    -

    -

    -

    \subsubsection{二分查找}

    \href{https://leetcode.cn/problems/binary-search/}{二分查找}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int search(vector<int>& nums, int target) {
        nums.emplace_back(INT_MAX);
        int left = 0, right = nums.size() - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }

        if (nums[left] == target) return left;
        else return -1;
    }
};
    \end{lstlisting}

    \subsubsection{搜索插入位置}

    \href{https://leetcode.cn/problems/search-insert-position/}{搜索插入位置}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        nums.emplace_back(INT_MAX);

        int left = 0, right = nums.size() - 1;

        while (left < right) {  // >= target 中最小的
            int mid = (left + right) / 2;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }

        return left;
    }
};
    \end{lstlisting}
    
    \subsubsection{剑指 Offer 53 - I. 在排序数组中查找数字 I}

    \href{https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/}{剑指 Offer 53 - I. 在排序数组中查找数字 I}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return 0;
        if (nums[0] > target) return 0;
        if (*(nums.end() - 1) < target) return 0;

        int left = 0, right = nums.size() - 1;

        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] < target) left = mid;
            else right = mid - 1;
        }

        int begin = nums[left] < target ? left + 1 : left;

        left = 0, right = nums.size() - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) right = mid;
            else left = mid + 1;
        }

        int end = nums[left] > target ? left - 1 : left;
        
        if (nums[begin] != target || nums[end] != target) return 0;

        return end - begin + 1;
    }  // 写的比较臃肿、混乱
};
    \end{lstlisting}

    \subsubsection{x 的平方根}

    \href{https://leetcode.cn/problems/sqrtx/}{x 的平方根}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int mySqrt(int x) {
        long long left = 0, right = x;

        while (left < right) {
            long long mid = (left + right + 1) / 2;
            if (mid * mid <= x) left = mid;  // 二分
            else right = mid - 1;
        }

        return left;
    }
};
    \end{lstlisting}

    \subsubsection{有效的完全平方数}

    \href{https://leetcode.cn/problems/valid-perfect-square/}{有效的完全平方数}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool isPerfectSquare(int num) {
        int left = 0, right = num;

        while (left < right) {
            long long mid = ((long long)left + right + 1) / 2;
            if (mid * mid <= num) left = mid;  // 二分答案判定
            else right = mid - 1;
        }

        return left * left == num;
    }
};
    \end{lstlisting}

    \subsection{数组，双指针}

    \subsubsection{删除有序数组中的重复项}

    \href{https://leetcode.cn/problems/remove-duplicates-from-sorted-array/}{删除有序数组中的重复项}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {  // 双指针
        int ins_pos = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != nums[ins_pos]) {
                ins_pos += 1;
                nums[ins_pos] = nums[i];
            }
        }

        return ins_pos + 1;
    }
};        
    \end{lstlisting}

    \subsubsection{移动零}

    \href{https://leetcode.cn/problems/move-zeroes/}{移动零}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int zero_pos = 0;  // 双指针

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != 0) {
                if (i == zero_pos) {
                    ++zero_pos;
                } else {
                    int tmp = nums[i];
                    nums[i] = nums[zero_pos];
                    nums[zero_pos] = tmp;
                    ++zero_pos;
                }
            }
        }
    }
};
    \end{lstlisting}

    \subsubsection{比较含退格的字符串}

    \href{https://leetcode.cn/problems/backspace-string-compare/}{比较含退格的字符串}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool backspaceCompare(string s, string t) {  // 双指针，倒序比较
        int a = s.length() - 1;
        int b = t.length() - 1;
        int cnt1 = 0, cnt2 = 0;

        while (a >= 0 || b >= 0) {
            while (a >= 0 ) {
                if (s[a] == '#') {
                    --a;
                    ++cnt1;
                } else if (cnt1 > 0) {
                    --a;
                    --cnt1;
                } else {
                    break;
                }
            }
            while (b >= 0) {
                if (t[b] == '#') {
                    --b;
                    ++cnt2;
                } else if (cnt2 > 0) {
                    --b;
                    --cnt2;
                } else {
                    break;
                }
            }

            if (a >= 0 && b >= 0) {
                if (s[a] != t[b]) return false;
            } else if (a >= 0 || b >= 0) {
                return false;
            }
            --a;
            --b;
        }
        return true;
    }
};
    \end{lstlisting}

    \subsubsection{有序数组的平方}

    \href{https://leetcode.cn/problems/squares-of-a-sorted-array/}{有序数组的平方}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ans(nums.size());
        int a = 0, b = nums.size() - 1, idx = nums.size() - 1;

        while (a <= b) {
            int tmp_a = nums[a] * nums[a], tmp_b = nums[b] * nums[b];

            if (tmp_a > tmp_b) {
                ans[idx] = tmp_a;
                --idx;
                ++a;
            } else {
                ans[idx] = tmp_b;
                --idx;
                --b;
            }
        }
        // 双指针，一个在begin，一个在end
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{移除元素}

    \href{https://leetcode.cn/problems/remove-element/}{移除元素}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int val_pos = 0;

        for (int now = 0; now < nums.size(); ++now) {
            if (nums[now] != val) {
                if (val_pos == now) ++val_pos;
                else {
                    int tmp = nums[now];
                    nums[now] = nums[val_pos];
                    nums[val_pos] = tmp;
                    ++val_pos;
                }
            }
        }

        return val_pos;
    }
};
    \end{lstlisting}

    \subsection{数组，滑动窗口}

    \subsubsection{长度最小的子数组}

    \href{https://leetcode.cn/problems/minimum-size-subarray-sum/}{长度最小的子数组}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int first = 0, s = 0, ans = INT_MAX;

        for (int last = 0; last < nums.size(); ++last) {
            s += nums[last];

            while (s >= target) {  // 滑动窗口
                ans = min(ans, last - first + 1);
                s -= nums[first];
                ++first;
            }
        }

        if (ans == INT_MAX) return 0;
        else return ans;
    }
};
    \end{lstlisting}

    \subsubsection{水果成篮}

    \href{https://leetcode.cn/problems/fruit-into-baskets/}{水果成篮}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        map<int, int> mp;

        int ans = 0;
        int left = 0, right = 0;
        for (; right < fruits.size(); ++right) {
            mp[fruits[right]] += 1;

            while (mp.size() > 2) { // 滑动窗口
                mp[fruits[left]] -= 1;
                if (mp[fruits[left]] == 0) mp.erase(mp.find(fruits[left]));
                ++left;
            }

            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{最小覆盖字串}

    \href{https://leetcode.cn/problems/minimum-window-substring/}{最小覆盖字串}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    bool match(int sub[], int t[]) {
        for (int i = 0; i < 256; ++i) if (sub[i] < t[i]) return false;
        return true;
    }
public:
    string minWindow(string s, string t) {
        int cnt_t[256] = {}, cnt_sub[256] = {};
        for (auto& c : t) cnt_t[int(c)] += 1;

        int first = 0, ans_first = -1, ans_last = -1;

        for (int last = 0; last < s.size(); ++last) {
            cnt_sub[s[last]] += 1;  // 滑动窗口

            while (this->match(cnt_sub, cnt_t)) {
                if (ans_first == -1 || ans_last - ans_first + 1 > last - first + 1) {
                    ans_first = first;
                    ans_last = last;
                }
                cnt_sub[s[first]] -= 1;
                ++first;
            }
        }

        if (ans_first == -1) return "";
        else return s.substr(ans_first, ans_last - ans_first + 1);
    }
};
    \end{lstlisting}

    \subsection{数组，大模拟，螺旋矩阵}

    \subsubsection{螺旋矩阵II}

    \href{https://leetcode.cn/problems/spiral-matrix-ii/}{螺旋矩阵II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int> (n, 0));
        int row = 0, col = 0, len = n, num = 1;
        while (num < n * n) {
            // 左上角到右上角 [)
            for (int i = 0; i < len - 1; ++i) ans[row][col + i] = num++;
            // 右上角到右下角 [)
            for (int i = 0; i < len - 1; ++i) ans[row + i][col + len - 1] = num++;
            // 右下角到左下角 [)
            for (int i = len - 1; i > 0; --i) ans[row + len - 1][col + i] = num++;
            // 左下角到左上角 [)
            for (int i = len - 1; i > 0; --i) ans[row + i][col] = num++;

            ++row;
            ++col;
            len -= 2;
        }

        if (n % 2 == 1) ans[n / 2][n / 2] = n * n;

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{螺旋矩阵}

    \href{https://leetcode.cn/problems/spiral-matrix/}{螺旋矩阵}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        const int n = matrix.size(), m = matrix[0].size();
        vector<int> ans(n * m);
        int row = 0, col = 0, all_row = n, all_col = m, idx = 0;

        while (idx < n * m - 1) {
            // 左上角到右上角 [)
            for (int i = 0; i < all_col - 1 && idx < n * m; ++i) ans[idx++] = matrix[row][col + i];
            // 右上角到右下角 [)
            for (int i = 0; i < all_row - 1 && idx < n * m; ++i) ans[idx++] = matrix[row + i][col + all_col - 1];
            // 右下角到左下角 [)
            for (int i = all_col - 1; i > 0 && idx < n * m; --i) ans[idx++] = matrix[row + all_row - 1][col + i];
            // 左下角到左上角 [)
            for (int i = all_row - 1; i > 0 && idx < n * m; --i) ans[idx++] = matrix[row + i][col];

            ++row;
            ++col;
            all_row -= 2;
            all_col -= 2;
        }

        if (n == m && n % 2 == 1) ans[idx] = matrix[n / 2][m / 2];
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{剑指 Offer 29. 顺时针打印矩阵}

    \href{https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/}{剑指 Offer 29. 顺时针打印矩阵}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// 同上
    \end{lstlisting}

    \subsection{链表}

    \subsubsection{移除链表元素}

    \href{https://leetcode.cn/problems/remove-linked-list-elements/}{移除链表元素}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* v_head = new ListNode();  // 虚拟头节点
        ListNode* pre = v_head;
        ListNode* now = head;
        pre->next = head;

        while (now) {
            if (now->val == val) {
                pre->next = now->next;
                delete now;
                now = pre->next;
            } else {
                pre = now;
                now = pre->next;
            }
        }

        ListNode* ans = v_head->next;
        delete v_head;
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{设计链表}

    \href{https://leetcode.cn/problems/design-linked-list/}{设计链表}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Node {  // 2022年9月23日
public:
    int value = 0;
    Node* next = nullptr;
    Node* prev = nullptr;

    Node(int value, Node* next, Node* prev) {
        this->value = value;
        this->next = next;
        this->prev = prev;
    }
};

class MyLinkedList {
public:
    Node* first;
    Node* last;

    MyLinkedList() {
        this->first = new Node(-1, nullptr, nullptr);
        this->last = new Node(-1, nullptr, nullptr);

        this->first->next = last;
        this->last->prev = first;
    }

    int get(int index) {
        auto now = this->first;

        index += 1;
        while (index-- && now != this->last) {
            now = now->next;
        }
        return now->value;
    }

    void addAtHead(int val) {
        Node* new_head = new Node(val, nullptr, nullptr);
        Node* old_head = first->next;

        this->first->next = new_head;
        new_head->prev = this->first;

        new_head->next = old_head;
        old_head->prev = new_head;
    }

    void addAtTail(int val) {
        Node* new_tail = new Node(val, nullptr, nullptr);
        Node* old_tail = this->last->prev;

        new_tail->next = this->last;
        this->last->prev = new_tail;

        old_tail->next = new_tail;
        new_tail->prev = old_tail;
    }

    void addAtIndex(int index, int val) {
        Node* prev_node = first;

        while (index-- && prev_node != this->last) {
            prev_node = prev_node->next;
        }

        if (prev_node == this->last) return;

        Node* next_node = prev_node->next;
        Node* new_node = new Node(val, nullptr, nullptr);

        prev_node->next = new_node;
        new_node->prev = prev_node;

        new_node->next = next_node;
        next_node->prev = new_node;

    }

    void deleteAtIndex(int index) {
        Node* del_node = first;

        index += 1;
        while (index-- && del_node != this->last) {
            del_node = del_node->next;
        }

        if (del_node == this->last) return;

        Node* left_node = del_node->prev;
        Node* right_node = del_node->next;

        left_node->next = right_node;
        right_node->prev = left_node;
        delete del_node;
    }
};
    \end{lstlisting}

    \subsubsection{反转链表}

    \href{https://leetcode.cn/problems/reverse-linked-list/}{反转链表}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    ListNode* ans = nullptr;
    void solve(ListNode* now) {
        if (!now) return;
        solve(now->next);
        ans->next = now;
        ans = ans->next;
    }
public:
    ListNode* reverseList(ListNode* head) {
        this->ans = new ListNode(-1);
        ListNode* res = ans;
        this->solve(head);  // 递归写法，有些乱
        ans->next = nullptr;
        this->ans = res->next;
        delete res;
        return this->ans;
    }
};
    \end{lstlisting}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* tmp = nullptr;
        ListNode* now = head;  //  双指针，反转链表

        while (now) {
            tmp = now->next;
            now->next = pre;  // 反转，很直观
            pre = now;
            now = tmp;
        }
        
        return pre;
    }
};
    \end{lstlisting}

    \subsubsection{两两交换链表中的节点}

    \href{https://leetcode.cn/problems/swap-nodes-in-pairs/}{两两交换链表中的节点}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
    if (not head) return head;
    if (not head->next) return head;

    ListNode* pre = nullptr;
    ListNode* ans = head->next;
    while (head and head->next) {
        auto a = head, b = head->next;
        head = head->next->next;

        a->next = b->next;
        b->next = a;  // 两个节点完成交换
        if (pre) pre->next = b;  // 接上前面的

        pre = a;
    }
    return ans;
}
};
    \end{lstlisting}

    \subsubsection{删除链表的倒数第N个结点}

    \href{https://leetcode.cn/problems/remove-nth-node-from-end-of-list/}{删除链表的倒数第N个结点}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *v_head = new ListNode(-1, head);
        ListNode *fast = v_head, *slow = v_head;  //  快慢指针法

        for (int i = 0; i < n + 1; ++i) fast = fast->next;
        while (fast) fast = fast->next, slow = slow->next;

        ListNode *tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;

        ListNode *ans = v_head->next;
        delete v_head;
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{链表相交}

    \href{https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/}{链表相交}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  // 两次遍历
        int cnt_a = 0, cnt_b = 0;
        ListNode *a = headA, *b = headB;

        while (a) ++cnt_a, a = a->next;
        while (b) ++cnt_b, b = b->next;

        a = headA;
        b = headB;

        while (cnt_a > cnt_b) --cnt_a, a = a->next;
        while (cnt_b > cnt_a) --cnt_b, b = b->next;

        while (cnt_a--) {
            if (a == b) return a;
            a = a->next;
            b = b->next;
        }
        return nullptr;
    }
};
    \end{lstlisting}

    \subsubsection{环形链表 II}

    \href{https://leetcode.cn/problems/linked-list-cycle-ii/}{环形链表 II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return nullptr;  // 相关证明可以看代码随想录网页或者题解
        if (!head->next) return nullptr;

        ListNode* fast = head, *slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                ListNode* pos = head;
                while (pos != slow) {
                    pos = pos->next;
                    slow = slow->next;
                }
                return pos;
            }
        }
        return nullptr;
    }
};
    \end{lstlisting}

    \subsection{哈希表（Hash Table）}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.7]{Figures/Hash Table 1.png}
        \caption{C++ 中的集合}
    \end{figure}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.7]{Figures/Hash Table 2.png}
        \caption{C++ 中的集合}
    \end{figure}

    \subsubsection{有效的字母异位词}

    \href{https://leetcode.cn/problems/valid-anagram/}{有效的字母异位词}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> mp;
        for (char c : t) mp[c] += 1;
        for (char c : s) mp[c] -= 1;
        for (auto& p : mp) if (p.second != 0) return false;
        return true;
    }
};
    \end{lstlisting}

    \subsubsection{赎金信}

    \href{https://leetcode.cn/problems/ransom-note/}{赎金信}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mp;
        for (const char& c : magazine) mp[c] += 1;
        for (const char& c : ransomNote) mp[c] -= 1;
        for (const pair<char, int> p : mp) if (p.second < 0) return false;
        return true;
    }
};
    \end{lstlisting}

    \subsubsection{字母异位词分组}

    \href{https://leetcode.cn/problems/group-anagrams/}{字母异位词分组}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
    using ull = unsigned long long;
private:
    ull str_hash_code(string s) {
        ull res = 0;
        sort(s.begin(), s.end());  // 排序以后，做字符串哈希，P=131
        for (const char& c : s) res = res * 131 + (c - 'a' + 1);
        return res;
    }
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<ull, int> idx_mp;
        int idx = 0;

        for (const string& s : strs) {
            ull code = this->str_hash_code(s);
            if (idx_mp.find(code) == idx_mp.end()) {
                ans.emplace_back();
                idx_mp[code] = idx;
                ++idx;
            }
            ans[idx_mp[code]].emplace_back(s);
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{找到字符串中所有字母异位词}

    \href{https://leetcode.cn/problems/find-all-anagrams-in-a-string/}{找到字符串中所有字母异位词}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    bool check(const int arr[]) {
        for (int i = 0; i < 26; ++i) if (arr[i] != 0) return false;
        return true;
    }
public:
    vector<int> findAnagrams(string s, string p) {
        int cnt[26] = {};  // 还是哈希
        const int n = s.length(), m = p.length();
        vector<int> ans;
        if (n < m) return ans;

        for (int i = 0; i < m; ++i) {
            cnt[s[i] - 'a'] -= 1;
            cnt[p[i] - 'a'] += 1;
        }

        if (this->check(cnt)) ans.emplace_back(0);

        for (int i = m; i < n; ++i) {
            cnt[s[i] - 'a'] -= 1;
            cnt[s[i - m] - 'a'] += 1;
            if (this->check(cnt)) ans.emplace_back(i - m + 1);
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{两个数组的交集}

    \href{https://leetcode.cn/problems/intersection-of-two-arrays/}{两个数组的交集}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end());

        vector<int> ans;
        for (const int& i : s1) if (s2.find(i) != s2.end()) ans.emplace_back(i);

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{两个数组的交集 II}

    \href{https://leetcode.cn/problems/intersection-of-two-arrays-ii/}{两个数组的交集 II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        unordered_map<int, int> a, b;
        for (auto& i : nums1) a[i] += 1;
        for (auto& i : nums2) b[i] += 1;

        for (auto& p : a) {
            if (b.find(p.first) != b.end()) {
                int cnt = min(p.second, b[p.first]);
                while (cnt--) ans.emplace_back(p.first);
            }
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{快乐数}

    \href{https://leetcode.cn/problems/happy-number/}{快乐数}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
using ull = unsigned long long;
private:
ull calculate(ull i) {
    ull res = 0;
    while (i) {
        ull tmp = i % 10;
        i /= 10;
        res += tmp * tmp;
    }
    return res;
}
public:
bool isHappy(int n) {
    unordered_set<ull> st;
    ull num = n;

    while (num != 1) {
        if (st.find(num) != st.end()) return false;
        else st.insert(num);
        num = this->calculate(num);
    }
    return true;
}
};        
    \end{lstlisting}

    \subsubsection{两数之和}

    \href{https://leetcode.cn/problems/two-sum/}{两数之和}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); ++i) {
            if (mp.find(target - nums[i]) != mp.end()) {
                return { mp[target - nums[i]], i };
            } else {
                mp[nums[i]] = i;
            }
        }
        return { 0, 0 };
    }
};
    \end{lstlisting}

    \subsubsection{四数相加 II}

    \href{https://leetcode.cn/problems/4sum-ii/}{四数相加 II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int ans = 0;
        unordered_map<int, int> mp;
        for (auto& i : nums1)
            for (auto& j : nums2)
                mp[i + j] += 1;
        for (auto& i : nums3)
            for (auto& j : nums4)
                if (mp.find(- i - j) != mp.end())
                    ans += mp[- i - j];
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{三数之和}

    \href{https://leetcode.cn/problems/3sum/}{三数之和}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// 这道题用双指针做好，有有一点烦的去重
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) continue;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) --right;
                else if (nums[i] + nums[left] + nums[right] < 0) ++left;
                else {
                    ans.emplace_back(vector<int> { nums[i], nums[left], nums[right] });
                    while (left < right && nums[right] == nums[right - 1]) --right;
                    while (left < right && nums[left]  == nums[left + 1]) ++left;
                    --right;
                    ++left;
                }
            }
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{四数之和}

    \href{https://leetcode.cn/problems/4sum/}{四数之和}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// 还是双指针，把n^4优化到n^3，注意剪枝和数据类型
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        const int& n = nums.size();

        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if ((long long)nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if ((long long)nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue;

                int left = j + 1, right = n - 1;
                while (left < right) {
                    if ((long long)nums[i] + nums[j] + nums[left] + nums[right] > target) --right;
                    else if ((long long)nums[i] + nums[j] + nums[left] + nums[right] < target) ++left;
                    else {
                        ans.emplace_back(vector<int> {nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) ++left;
                        while (left < right && nums[right] == nums[right - 1]) -- right;
                        ++left;
                        --right;
                    }
                }
            }
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsection{字符串、KMP算法}

    KMP算法，又称\textbf{模式匹配算法}，能够在线性的时间内，判断字符串 $ A[1, N] $ 是否为字符串 $ B[1, M] $ 的子串，并求出A在B中出现的每个位置，时间复杂度 $ \Theta (NM) $ 。

    （其实，这个问题使用字符串哈希也能在线性的时间内求解，但是KMP更加高效、准确，且能提供更多的信息）

    \paragraph{KMP算法一共分两步}~{}

    \textbf{1、对字符串A进行自我匹配}，即，求解一个数组next，其中，$ next[i] $ 表示A中以i结尾的\textbf{非前缀}子串与A的\textbf{前缀}能够匹配的最长长度，即：

    \begin{equation}
        next[i] = \max\{j\}, \mbox{其中}j < i, \mbox{且} A[1, j] = A[i - j + 1, i]
    \end{equation}

    \textbf{2、对字符串A和字符串B进行匹配}，即，求解一个数组f，其中，$f[i]$表示B中以i结尾的\textbf{子串}，与A的\textbf{前缀}，能够匹配的最长长度，即：

    \begin{equation}
        f[i] = \max\{j\}, \mbox{其中} j \le i, \mbox{且} A[1, j] = B[i - j + 1, i]
    \end{equation}

    现在，假设我们，对字符串，a，b，a，b，a，b，a，a，c，求取next数组：

    一一，一一一一，一一一一，1，2，3，4，5，6，7，8，9

    next[1] = 0;

    next[2] = 0;
    
    next[3] = 1;

    next[4] = 2;
    
    next[5] = 3;

    next[6] = 4;

    当我们需要求解next[7]时，此时i=7，j=4，next[6] = 4，在此基础上我们发现A[i] = A[j + 1]，即A[7] = A[5]，所以next[7] = next[6] + 1 = 5;

    next[7] = 5;

    现在我们求解next[8]，此时不满足next[i] = next[j + 1]的条件，即不满足next[6] = next[8]，不能直接在原来的基础之上扩展了。所以，我们需要在i=7的位置上，寻找更短的满足next数组的“后缀等于前缀”条件的子串，来尝试扩展。

    同时，又由于next[7] = 5，即A[1, 5] = A[3, 7]，所以在i = 7的位置上寻找满足我们要求的更短的子串，就等于在i = 5的位置上寻找，即next[5]就记录了我们需要的子串。

    next[5] = 3，即i = 5，j = 3，此时还是不满足next[i] = next[j + 1]的条件，继续尝试next[3]，还是不满足，只能从0开始了，因为A[1] = A[8]，所以next[8] = 1。

    next[8] = 1;

    next[9] = 0;

    所以，求解next数组的代码如下：

    \begin{lstlisting}[language=C++, lineskip=3pt]
next[1] = 0;
for (int i = 2, j = 0; i <= n; ++i) {
    while (j > 0 && A[i] != A[j + 1]) j = next[j];
    if (A[i] = A[j + 1]) ++j;
    next[i] = j;
}
    \end{lstlisting}

    相似的，求解f数组的代码如下：

    \begin{lstlisting}[language=C++, lineskip=3pt]
for (int i = 1, j = 0; i <= m; ++i) {
    while (j > 0 && (j == n || B[i] != A[j + 1])) j = next[j];  // 如果j==n，说明匹配成功一次了，下次就回退一下，重新开始匹配
    if (B[i] == A[j + 1]) ++j;
    f[i] = j;
    if (f[i] == n) cout << "Sussess at " << i << endl;
}
    \end{lstlisting}

    （更进阶的字符串匹配算法还有BM算法）

    \subsubsection{找出字符串中第一个匹配的下标}

    \href{https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/}{找出字符串中第一个匹配的下标}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;

        needle = ' ' + needle;  // 为了完全匹配模板的写法，加了个空格
        haystack = ' ' + haystack;

        const int n = needle.size() - 1;
        const int m = haystack.size() - 1;
        vector<int> next(n + 1, 0);

        for (int i = 2, j = 0; i <= n; ++i) {
            while (j > 0 && needle[i] != needle[j + 1]) j = next[j];
            if (needle[i] == needle[j + 1]) ++j;
            next[i] = j;
        }

        for (int i = 1, j = 0; i <= m; ++i) {
            while (j > 0 && haystack[i] != needle[j + 1]) j = next[j];
            if (haystack[i] == needle[j + 1]) ++j;
            if (j == n) return i - n;
        }
        return -1;
    }
};
    \end{lstlisting}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
    public:
        int strStr(string haystack, string needle) {
            if (needle.empty()) return 0;
    
            const int n = needle.size();
            const int m = haystack.size();
            vector<int> next(n + 1, 0);
    
            for (int i = 2, j = 0; i <= n; ++i) {
                while (j > 0 && needle[i - 1] != needle[j]) j = next[j];  // 访问字符串时，下标都减掉1，来匹配从1开始的下标；
                if (needle[i - 1] == needle[j]) ++j;
                next[i] = j;
            }
    
            for (int i = 1, j = 0; i <= m; ++i) {
                while (j > 0 && haystack[i - 1] != needle[j]) j = next[j];
                if (haystack[i - 1] == needle[j]) ++j;
                if (j == n) return i - n;
            }
            return -1;
        }
    };
    \end{lstlisting}

    \subsubsection{重复的子字符串}

    \href{https://leetcode.cn/problems/repeated-substring-pattern/}{重复的子字符串}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// 该方法完整的正确性（充分+必要）参见LeetCode题解
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        const int n = s.size();
        vector<int> next(n + 1, 0);

        for (int i = 2, j = 0; i <= n; ++i) {
            while (j > 0 && s[i - 1] != s[j]) j = next[j];
            if (s[i - 1] == s[j]) ++j;
            next[i] = j;
        }

        if (next[n] == 0) return false;  // 没有匹配，一定不是
        const int m = n - next[n];  // 循环节的长度
        if (n % m != 0) return false;  // 必须整除
        // for (int i = 0; i + m < n; ++i) if (s[i] != s[i + m]) return false;  // 其实不必要
        return true;
    }
};
    \end{lstlisting}

    \subsubsection{反转字符串}

    \href{https://leetcode.cn/problems/reverse-string/}{反转字符串}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    void reverseString(vector<char>& s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l] != s[r]) swap(s[l], s[r]);
            ++l;
            --r;
        }
    }
};
    \end{lstlisting}

    \subsubsection{反转字符串 II}

    \href{https://leetcode.cn/problems/reverse-string-ii/}{反转字符串 II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    inline void my_reverse(string& s, int l, int r) {
        while (l < r) {
            char tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
            ++l;
            --r;
        }
    }
public:
    string reverseStr(string s, int k) {
        int l = 0, r = k - 1;

        while (l < s.length()) {
            r = min(r, (int)s.length() - 1);
            this->my_reverse(s, l, r);
            l += 2 * k;
            r += 2 * k;
        }

        return s;
    }
};
    \end{lstlisting}

    \subsubsection{替换空格}

    \href{https://leetcode.cn/problems/ti-huan-kong-ge-lcof/}{替换空格}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// 原地扩容 + 双指针
class Solution {
public:
    string replaceSpace(string s) {
        const int old_n = s.size();
        int cnt = 0;
        for (const char& c : s) if (c == ' ') ++cnt;

        s.resize(old_n + 2 * cnt);
        const int new_n = s.size();

        int fast = old_n - 1, slow = new_n - 1;
        while (fast >= 0) {
            if (s[fast] != ' ') {
                s[slow] = s[fast];
                --slow;
                --fast;
            } else {
                s[slow] = '0';
                s[slow - 1] = '2';
                s[slow - 2] = '%';
                slow -= 3;
                --fast;
            }
        }

        return s;
    }
};
    \end{lstlisting}

    \subsubsection{反转字符串中的单词}

    \href{https://leetcode.cn/problems/reverse-words-in-a-string/}{反转字符串中的单词}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// 懒得不行的暴力写法，不想追求O(1)的空间了
class Solution {
public:
    string reverseWords(string s) {
        string ans, tmp;
        stack<string> st;
        s += ' ';

        for (const char& c : s) {
            if (c == ' ' && !tmp.empty()) {
                st.push(tmp);
                tmp.clear();
            } else if (c != ' ') {
                tmp += c;
            }
        }

        while (!st.empty()) {
            ans += st.top();
            st.pop();
            if (!st.empty()) ans += ' ';
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{左旋转字符串}

    \href{https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/}{左旋转字符串}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    void reverse(string& s, int l, int r) {
        while (l < r) {
            char tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
            ++l;
            --r;
        }
    }
public:
    string reverseLeftWords(string s, int k) {
        // 先反转 [1, n]
        // 再反转 [1, n - k]
        // 最后反转 [n - k + 1, n]
        const int n = s.length();
        this->reverse(s, 0, n - 1);
        this->reverse(s, 0, n - k - 1);
        this->reverse(s, n - k, n - 1);
        return s;
    }
};
    \end{lstlisting}

    \subsection{栈、队列}

    STL中栈往往不被归类为容器，而被归类为Container Adapter（容器适配器）。C++的STL中，栈的底层实现可以是Vector、Deque、List，默认为Deque。

    \subsubsection{用栈实现队列}

    \href{https://leetcode.cn/problems/implement-queue-using-stacks/}{用栈实现队列}

    分成两个栈，一个in，一个out，输入的元素压入in，当需要弹出元素的时候，将in中的元素全部依次弹出，并压入到out中，这样，out栈顶的元素就是最开始输入的元素。

    当out为空时，才需要再次将in中的元素压入out。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class MyQueue {
private:
    stack<int> in_stack, out_stack;
    inline void in2out() {
        while (!in_stack.empty()) {
            out_stack.push(in_stack.top());
            in_stack.pop();
        }
    }
public:
    MyQueue() {
        
    }

    void push(int x) {
        in_stack.push(x);
    }

    int pop() {
        if (out_stack.empty()) in2out();
        int tmp = out_stack.top();
        out_stack.pop();
        return tmp;
    }

    int peek() {
        if (out_stack.empty()) in2out();
        return out_stack.top();
    }

    bool empty() {
        return in_stack.empty() && out_stack.empty();
    }
};
    \end{lstlisting}

    \subsubsection{用队列实现栈}

    \href{https://leetcode.cn/problems/implement-stack-using-queues/}{用队列实现栈}

    只用一个队列来模拟即可，要弹出栈顶的元素时，将队列中前n - 1个元素一次弹出，再添加到队列尾部，这样队列头部的元素就是最新入队的元素，即“栈顶”的元素。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class MyStack {
private:
    queue<int> q;
public:
    MyStack() {

    }

    void push(int x) {
        q.push(x);
    }

    int pop() {
        int n = q.size() - 1;
        while (n--) {
            q.push(q.front());
            q.pop();
        }
        int res = q.front();
        q.pop();
        return res;
    }

    int top() {
        return q.back();
    }

    bool empty() {
        return q.empty();
    }
};
    \end{lstlisting}

    \subsubsection{有效的括号}

    \href{https://leetcode.cn/problems/valid-parentheses/}{有效的括号}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (auto c : s) {
            if (c == '(' or c == '[' or c == '{') {
                st.push(c);
            } else if (c == ')') {
                if (st.empty() or st.top() != '(') return false;
                else st.pop();
            } else if (c == ']') {
                if (st.empty() or st.top() != '[') return false;
                else st.pop();
            } else if (c == '}') {
                if (st.empty() or st.top() != '{') return false;
                else st.pop();
            }
        }
        return st.empty();
    }
};
    \end{lstlisting}

    \subsubsection{删除字符串中所有的相邻重复项}

    \href{https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/}{删除字符串中所有的相邻重复项}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    string removeDuplicates(string S) {
        string ans;
        for (const char& c : S) {
            if (!ans.empty() && ans.back() == c) ans.pop_back();
            else ans.push_back(c);
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{逆波兰表达式求值}

    \href{https://leetcode.cn/problems/evaluate-reverse-polish-notation/}{逆波兰表达式求值}

    中缀表达式；

    前缀表达式（波兰式），表达式树前序遍历；

    后缀表达式（逆波兰式），表达式树后序遍历；

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int str_to_int(const string& s) {
        int res = 0, idx = 0;
        bool negative = false;
        if (s[0] == '-') negative = true, idx = 1;
        for (; idx < s.length(); ++idx) {
            res = res * 10;
            res = res + (s[idx] - '0');
        }
        return negative ? -res : res;
    }
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (const string& s : tokens) {
            if (s == "+") {
                int a = st.top(); st.pop();
                int b = st.top(); st.pop();
                st.push(b + a);
            } else if (s == "-") {
                int a = st.top(); st.pop();
                int b = st.top(); st.pop();
                st.push(b - a);
            } else if (s == "*") {
                int a = st.top(); st.pop();
                int b = st.top(); st.pop();
                st.push(b * a);
            } else if (s == "/") {
                int a = st.top(); st.pop();
                int b = st.top(); st.pop();
                st.push(b / a);
            } else {
                st.push(this->str_to_int(s));
            }
        }
        return st.top();
    }
};
    \end{lstlisting}

    \subsubsection{滑动窗口最大值}

    \href{https://leetcode.cn/problems/sliding-window-maximum/}{滑动窗口最大值}

    使用优先队列，$ \Theta (n \log n) $ 的做法：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        priority_queue<pair<int, int>> q;

        for (int i = 0; i < k; ++i) q.push({ nums[i], i });
        ans.emplace_back(q.top().first);

        for (int i = k; i < nums.size(); ++i) {
            while (not q.empty() and q.top().second <= i - k) q.pop();
            q.push({ nums[i], i });
            ans.emplace_back(q.top().first);
        }

        return ans;
    }
};
    \end{lstlisting}

    使用单调队列，$ \Theta (n) $ 的做法：

    单调队列中，下标严格递增，值严格递减；

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
        }

        vector<int> ans { nums[q.front() ]};
        for (int i = k; i < nums.size(); ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) q.pop_back();
            q.push_back(i);
            while (q.front() < i - k + 1) q.pop_front();
            ans.emplace_back(nums[q.front()]);
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{前K个高频元素}

    \href{https://leetcode.cn/problems/top-k-frequent-elements/}{前K个高频元素}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        auto cmp = [](pair<int, int> a, pair<int, int>b) -> bool {
            return a.first > b.first;
        };

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
        map<int, int> count;
        vector<int> ans;

        for (int& i : nums) count[i] += 1;
        for (auto& p : count) {
            if (q.size() < k) {
                q.push({p.second, p.first});
                continue;
            }

            if (q.top().first < p.second) {
                q.pop();
                q.push({p.second, p.first});
            }
        }

        while (!q.empty()) {
            ans.emplace_back(q.top().second);
            q.pop();
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsection{二叉树}

    满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树（AVL Tree）；

    链式存储、顺序存储；

    前序（根节点，左子树，右子树）、中序（左子树，根节点，右子树）、后序（左子树，右子树，根节点）、层序，遍历；

    前序+中序，或者，后序+中序遍历的结果，可用于重建原本的二叉树。

    \subsubsection{二叉树的前序遍历}

    \href{https://leetcode.cn/problems/binary-tree-preorder-traversal/}{二叉树的前序遍历}

    \begin{lstlisting}[language=C++, lineskip=3pt]
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    vector<int> ans;

    void dfs(TreeNode* now) {
        if (now == nullptr) return;
        this->ans.emplace_back(now->val);
        dfs(now->left);
        dfs(now->right);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        this->dfs(root);
        return this->ans;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的中序遍历}

    \href{https://leetcode.cn/problems/binary-tree-inorder-traversal/}{二叉树的中序遍历}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<int> ans;
    void dfs(TreeNode* now) {
        if (now == nullptr) return;
        dfs(now->left);
        this->ans.emplace_back(now->val);
        dfs(now->right);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return this->ans;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的后序遍历}

    \href{https://leetcode.cn/problems/binary-tree-postorder-traversal/}{二叉树的后序遍历}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<int> ans;
    void dfs(TreeNode* now) {
        if (now == nullptr) return;
        dfs(now->left);
        dfs(now->right);
        this->ans.emplace_back(now->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        this->dfs(root);
        return this->ans;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的层序遍历}

    \href{https://leetcode.cn/problems/binary-tree-level-order-traversal/}{二叉树的层序遍历}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;

        queue<pair<TreeNode*, int>> q;
        q.push({ root, 0 });

        while (!q.empty()) {
            auto now = q.front(); q.pop();

            if (now.second < ans.size()) ans[now.second].emplace_back(now.first->val);
            else {
                ans.emplace_back();
                ans[now.second].emplace_back(now.first->val);
            }

            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的右视图}

    \href{https://leetcode.cn/problems/binary-tree-right-side-view/}{二叉树的右视图}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// 还是一道层序遍历的题目
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        queue<pair<TreeNode*, int>> q;

        if (root == nullptr) return ans;
        else q.push({ root, 0 });

        while (!q.empty()) {
            auto now = q.front(); q.pop();

            if (ans.size() > now.second) ans[now.second] = now.first->val;
            else ans.emplace_back(now.first->val);

            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的层平均值}

    \href{https://leetcode.cn/problems/average-of-levels-in-binary-tree/}{二叉树的层平均值}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// BFS、DFS，均可
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (!root) return {};

        vector<double> ans;
        map<int, long long> cnt, sum;
        queue<pair<TreeNode*, int>> q;

        q.push({ root, 0 });
        while (!q.empty()) {
            auto now = q.front(); q.pop();
            cnt[now.second] += 1;
            sum[now.second] += now.first->val;

            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }

        for (const auto& p : cnt) ans.emplace_back((double)sum[p.first] / p.second);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{N 叉树的层序遍历}

    \href{https://leetcode.cn/problems/n-ary-tree-level-order-traversal/}{N 叉树的层序遍历}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;

        if (!root) return ans;
        queue<pair<Node*, int>> q;
        q.push({ root, 0 });

        while (!q.empty()) {
            auto now = q.front(); q.pop();

            if (now.second < ans.size()) ans[now.second].emplace_back(now.first->val);
            else {
                ans.emplace_back();
                ans[now.second].emplace_back(now.first->val);
            }

            for (auto& node : now.first->children) if (node) q.push({ node, now.second + 1 });
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{在每个树行中找最大值}

    \href{https://leetcode.cn/problems/find-largest-value-in-each-tree-row/}{在每个树行中找最大值}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (!root) return {};

        vector<int> ans;
        queue<pair<TreeNode*, int>> q;

        q.push({ root, 0 });
        while (!q.empty()) {
            auto now = q.front(); q.pop();

            if (now.second >= ans.size()) ans.emplace_back(now.first->val);
            else ans[now.second] = max(ans[now.second], now.first->val);

            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{填充每个节点的下一个右侧节点}

    \href{https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/}{填充每个节点的下一个右侧节点}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;

        vector<Node*> last;
        queue<pair<Node*, int>> q;

        q.push({ root, 0 });
        while (!q.empty()) {
            auto now = q.front(); q.pop();
            now.first->next = nullptr;

            if (last.size() <= now.second) last.emplace_back(now.first);
            else {
                last[now.second]->next = now.first;
                last[now.second] = now.first;
            }

            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }

        return root;
    }
};
    \end{lstlisting}

    \subsubsection{填充每个节点的下一个右侧节点 II}

    \href{https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/}{填充每个节点的下一个右侧节点 II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;

        vector<Node*> last;
        queue<pair<Node*, int>> q;

        q.push({ root, 0 });
        while (!q.empty()) {
            auto now = q.front(); q.pop();
            now.first->next = nullptr;

            if (last.size() <= now.second) last.emplace_back(now.first);
            else {
                last[now.second]->next = now.first;
                last[now.second] = now.first;
            }

            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }

        return root;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的最大深度}

    \href{https://leetcode.cn/problems/maximum-depth-of-binary-tree/}{二叉树的最大深度}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;

        int ans = 0;
        queue<pair<TreeNode*, int>> q;
        q.push({ root, 1 });

        while (!q.empty()) {
            auto now = q.front(); q.pop();
            ans = max(ans, now.second);
            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的最小深度}

    \href{https://leetcode.cn/problems/minimum-depth-of-binary-tree/}{二叉树的最小深度}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;

        int ans = INT_MAX;
        queue<pair<TreeNode*, int>> q;
        q.push({ root, 1 });

        while (!q.empty()) {
            auto now = q.front(); q.pop();

            if (!now.first->left && !now.first->right) ans = min(ans, now.second);
            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{翻转二叉树}

    \href{https://leetcode.cn/problems/invert-binary-tree/}{翻转二叉树}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;

        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            auto now = q.front(); q.pop();
            auto tmp = now->left;
            now->left = now->right;
            now->right = tmp;

            if (now->left) q.push(now->left);
            if (now->right) q.push(now->right);
        }
        return root;
    }
};
    \end{lstlisting}

    \subsubsection{对称二叉树}

    \href{https://leetcode.cn/problems/symmetric-tree/}{对称二叉树}

    迭代做法如下：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> l, r;
        l.push(root);
        r.push(root);

        while (!l.empty() && !r.empty()) {
            auto ll = l.front(); l.pop();
            auto rr = r.front(); r.pop();

            if (ll == nullptr || rr == nullptr) {
                if (ll != rr) return false;
            } else if (ll->val != rr->val) {
                return false;
            }

            if (ll) {
                l.push(ll->left);
                l.push(ll->right);
            }

            if (rr) {
                r.push(rr->right);
                r.push(rr->left);
            }
        }

        return true;
    }
};
    \end{lstlisting}

    递归做法如下：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    bool dfs(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right != nullptr) return false;
        if (left != nullptr && right == nullptr) return false;
        if (left == nullptr && right == nullptr) return true;
        if (left->val != right->val) return false;
        return dfs(left->left, right->right) && dfs(left->right, right->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return this->dfs(root->left, root->right);
    }
};
    \end{lstlisting}

    \subsubsection{相同的树}

    \href{https://leetcode.cn/problems/same-tree/}{相同的树}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p != nullptr && q == nullptr) return false;
        if (p == nullptr && q != nullptr) return false;
        if (p == nullptr && q == nullptr) return true;
        if (p->val != q->val) return false;
        
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
    \end{lstlisting}

    \subsubsection{另一棵树的子树}

    \href{https://leetcode.cn/problems/subtree-of-another-tree/}{另一棵树的子树}

    暴力匹配做法：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    bool tree_compare(TreeNode* a, TreeNode* b) {
        if (a == nullptr && b != nullptr) return false;
        if (a != nullptr && b == nullptr) return false;
        if (a == nullptr && b == nullptr) return true;
        if (a->val != b->val) return false;
        return tree_compare(a->left, b->left) && tree_compare(a->right, b->right);
    }
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            auto now = st.top(); st.pop();
            if (tree_compare(now, subRoot)) return true;

            if (now) {
                if (now->left) st.push(now->left);
                if (now->right) st.push(now->right);
            }
        }
        return false;
    }
};
    \end{lstlisting}

    在深度优先搜索序列上，做串匹配（KMP）：

    \begin{lstlisting}[language=C++, lineskip=3pt]
// Template
class Solution {
private:
    vector<int> a {0}, b {0};
    void dfs(vector<int>& arr, TreeNode* now) {
        if (!now) return;
        arr.emplace_back(now->val);

        if (now->left) dfs(arr, now->left);
        else arr.emplace_back(INT_MIN);  // 需要将空的左节点或者右节点加入

        if (now->right) dfs(arr, now->right);
        else arr.emplace_back(INT_MAX);
    }
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        this->dfs(this->a, subRoot);  // 建立DFS序
        this->dfs(this->b, root);

        const int n = a.size() - 1, m = b.size() - 1;

        vector<int> next(n + 1, 0);  // KMP匹配
        for (int i = 2, j = 0; i <= n; ++i) {
            while (j > 0 && a[i] != a[j + 1]) j = next[j];
            if (a[i] == a[j + 1]) ++j;
            next[i] = j;
        }

        for (int i = 1, j = 0; i <= m; ++i) {
            while (j > 0 && b[i] != a[j + 1]) j = next[j];
            if (b[i] == a[j + 1]) ++j;
            if (j == n) return true;
        }

        return false;
    }
};
    \end{lstlisting}

    \subsubsection{完全二叉树的节点个数}

    \href{https://leetcode.cn/problems/count-complete-tree-nodes/}{完全二叉树的节点个数}

    利用完全二叉树的性质，递归到一定的深度，一定会有左子树或者右子树是满二叉树，且完全二叉树的任意一个子树也一定是完全二叉树。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;

        TreeNode *l = root->left, *r = root->right;
        int depth_l = 0, depth_r = 0;

        while (l) l = l->left, ++depth_l;
        while (r) r = r->right, ++depth_r;

        if (depth_l == depth_r) return (0x02 << depth_l) - 1;
        else return countNodes(root->left) + countNodes(root->right) + 1;
    }
};
    \end{lstlisting}

    \subsubsection{平衡二叉树}

    \href{https://leetcode.cn/problems/balanced-binary-tree/}{平衡二叉树}

    本题对平衡二叉树的定义为，“一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1”，在本题中，我先利用DFS，将每个节点的值修改为其高度（叶子节点高度为1，根节点高度为整棵树的深度），然后迭代检查每个节点的左右子树。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int mark_height(TreeNode* now) {
        if (!now->left && !now->right) {
            now->val = 1;  // 叶子节点高度为1
            return 1;
        } else if (now->left && !now->right) {
            now->val = mark_height(now->left) + 1;  // 只有一个子树的情况，高度为子树高度+1
            return now->val;
        } else if (!now->left && now->right) {
            now->val = mark_height(now->right) + 1;  // 只有一个子树的情况，高度为子树高度+1
            return now->val;
        } else {
            int l = mark_height(now->left);
            int r = mark_height(now->right);
            now->val = max(l, r) + 1;  // 两棵子树都有的情况，高度为两颗子树高度较高的一棵的高度+1
            return now->val;
        }
    }
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        mark_height(root);  // 标记高度

        stack<TreeNode*> st;
        st.push(root);

        while (!st.empty()) {
            auto now = st.top(); st.pop();  // 挨个检查节点
            if (!now->left && !now->right) continue;
            if (now->left && !now->right && now->left->val > 1) return false;
            if (!now->left && now->right && now->right->val > 1) return false;
            if (now->left && now->right && abs(now->left->val - now->right->val) > 1) return false;

            if (now->left) st.push(now->left);
            if (now->right) st.push(now->right);
        }
        return true;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的所有路径}

    \href{https://leetcode.cn/problems/binary-tree-paths/}{二叉树的所有路径}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<string> ans;
    void dfs(TreeNode* now, string p) {
        if (!now) return;

        if (!now->left && !now->right) {
            this->ans.emplace_back(p + to_string(now->val));
        } else {
            if (now->left) dfs(now->left, p + to_string(now->val) + "->");
            if (now->right) dfs(now->right, p + to_string(now->val) + "->");
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode *root) {
        dfs(root, "");
        return this->ans;
    }
};

    \end{lstlisting}

    \subsubsection{左叶子之和}

    \href{https://leetcode.cn/problems/sum-of-left-leaves/}{左叶子之和}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int sumOfLeftLeaves(TreeNode *root) {
        int ans = 0;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* now = q.front();
            q.pop();

            if (now == nullptr) continue;
            if (now->left != nullptr) q.push(now->left);
            if (now->right != nullptr) q.push(now->right);
            if (now->left == nullptr) continue;
            if (now->left->left == nullptr and now->left->right == nullptr) ans += now->left->val;
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{树左下角的值}

    \href{https://leetcode.cn/problems/find-bottom-left-tree-value/}{树左下角的值}

    层序遍历求解：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        vector<int> res;
        queue<pair<TreeNode*, int>> q;
        q.push({ root, 0 });

        while (!q.empty()) {
            auto now = q.front(); q.pop();

            if (res.size() <= now.second) res.emplace_back(now.first->val);
            if (now.first->left) q.push({ now.first->left, now.second + 1 });
            if (now.first->right) q.push({ now.first->right, now.second + 1 });
        }

        return res.back();
    }
};
    \end{lstlisting}

    深度优先搜索求解：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int max_depth = 0, res = -1;
    void dfs(TreeNode* now, int depth) {
        if (depth > max_depth) {
            max_depth = depth;
            res = now->val;
        }
        if (now->left) dfs(now->left, depth + 1);
        if (now->right) dfs(now->right, depth + 1);
    }
public:
    int findBottomLeftValue(TreeNode* root) {
        dfs(root, 1);
        return res;
    }
};
    \end{lstlisting}

    \subsubsection{路径总和}

    \href{https://leetcode.cn/problems/path-sum/}{路径总和}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;

        stack<pair<TreeNode*, int>> st;
        st.emplace(root, root->val);

        while (!st.empty()) {
            auto now = st.top().first;
            int s = st.top().second; st.pop();

            if (!now->left && !now->right) {
                if (s == sum) return true;
                else continue;
            }

            if (now->left) st.emplace(now->left, s + now->left->val);
            if (now->right) st.emplace(now->right, s + now->right->val);
        }
        return false;
    }
};
    \end{lstlisting}

    \subsubsection{路径总和II}

    \href{https://leetcode.cn/problems/path-sum-ii/}{路径总和II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    void solve(TreeNode* now, vector<int>& path, vector<vector<int>>& ans, int sum, const int& target) {
        if (now->left == nullptr && now->right == nullptr && sum == target) {
            ans.emplace_back(path);
            return;
        }

        if (now->left) {
            path.emplace_back(now->left->val);
            solve(now->left, path, ans, sum + now->left->val, target);
            path.pop_back();
        }

        if (now->right) {
            path.emplace_back(now->right->val);
            solve(now->right, path, ans, sum + now->right->val, target);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (root == nullptr) return {};
        vector<vector<int>> ans;
        vector<int> path { root->val };
        solve(root, path, ans, root->val, sum);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{从中序与后序遍历序列构造二叉树}

    \href{https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/}{从中序与后序遍历序列构造二叉树}

    总体的思路是：后序遍历序列的最后一个元素，是根节点，然后在中序遍历序列中寻找到根节点，左边就是左子树，右边就是右子树，然后就可以递归了。

    举例，中序【9，3，15，20，7】，后序【9，15，7，20，3】；

    可知，3为根节点，【9】为左子树，【15，20，7】为右子树；

    然后就可以分割中序序列和后序序列，然后递归；

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.empty()) return nullptr;

        int idx;
        for (idx = 0; idx < inorder.size(); ++idx) if (inorder[idx] == postorder.back()) break;  // 寻找根节点在中序序列中的位置

        auto root = new TreeNode(postorder.back());
        vector<int> left_inorder(inorder.begin(), inorder.begin() + idx);  // 分割中序序列
        vector<int> right_inorder(inorder.begin() + idx + 1, inorder.end());

        vector<int> left_postorder(postorder.begin(), postorder.begin() + idx);  // 分割后序序列
        vector<int> right_postorder(postorder.begin() + idx, postorder.end() - 1);

        root->left = buildTree(left_inorder, left_postorder);  // 递归求解
        root->right = buildTree(right_inorder, right_postorder);
        return root;
    }
};
    \end{lstlisting}

    \subsubsection{从前序与中序遍历序列构造二叉树}

    \href{https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/}{从前序与中序遍历序列构造二叉树}

    做法类似上面，同理。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return nullptr;

        int idx;
        for (idx = 0; idx < preorder.size(); ++idx) if (inorder[idx] == preorder.front()) break;  // 寻找根节点位置

        auto root = new TreeNode(preorder.front());
        vector<int> left_preorder(preorder.begin() + 1, preorder.begin() + 1 + idx);  // 分割后序序列
        vector<int> right_preorder(preorder.begin() + 1 + idx, preorder.end());

        vector<int> left_inorder(inorder.begin(), inorder.begin() + idx);  // 分割中序序列
        vector<int> right_inorder(inorder.begin() + idx + 1, inorder.end());

        root->left = buildTree(left_preorder, left_inorder);  // 递归
        root->right = buildTree(right_preorder, right_inorder);
        return root;
    }
};
    \end{lstlisting}

    \subsubsection{最大二叉树}

    \href{https://leetcode.cn/problems/maximum-binary-tree/}{最大二叉树}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        // for (int i : nums) cerr << i << " "; cerr << endl;

        if (nums.empty()) return nullptr;

        int idx = 0;
        for (int i = 1; i < nums.size(); ++i) if (nums[i] > nums[idx]) idx = i;
        auto root = new TreeNode(nums[idx]);

        vector<int> left(nums.begin(), nums.begin() + idx);
        vector<int> right(nums.begin() + idx + 1, nums.end());

        root->left= constructMaximumBinaryTree(left);
        root->right = constructMaximumBinaryTree(right);
        return root;
    }
};
    \end{lstlisting}

    \subsubsection{合并二叉树}

    \href{https://leetcode.cn/problems/merge-two-binary-trees/}{合并二叉树}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 && root2) {
            auto root = new TreeNode(root1->val + root2->val);
            root->left = mergeTrees(root1->left, root2->left);
            root->right = mergeTrees(root1->right, root2->right);
            return root;
        } else if (root1) {
            auto root = new TreeNode(root1->val);
            root->left = mergeTrees(root1->left, nullptr);
            root->right = mergeTrees(root1->right, nullptr);
            return root;
        } else if (root2) {
            auto root = new TreeNode(root2->val);
            root->left = mergeTrees(nullptr, root2->left);
            root->right = mergeTrees(nullptr, root2->right);
            return root;
        } else {
            return nullptr;
        }
    }
};
    \end{lstlisting}

    \subsubsection{二叉搜索树中的搜索}

    \href{https://leetcode.cn/problems/search-in-a-binary-search-tree/}{二叉搜索树中的搜索}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return nullptr;
        else if (root->val == val) return root;
        else if (root->val < val) return searchBST(root->right, val);
        else return searchBST(root->left, val);
    }
};
    \end{lstlisting}

    \subsubsection{验证二叉搜索树}

    \href{https://leetcode.cn/problems/validate-binary-search-tree/}{验证二叉搜索树}

    有效的二叉搜索树定义如下：

    \begin{itemize}
        \item 节点的左子树只包含 \textbf{小于} 当前节点的数。
        \item 节点的右子树只包含 \textbf{大于} 当前节点的数。
        \item 所有左子树和右子树自身必须也是二叉搜索树。
    \end{itemize}

    思路：中序遍历序列为单调递增的。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<int> seq;
    void dfs(TreeNode* now) {
        if (!now) return;
        if (now->left) dfs(now->left);
        seq.emplace_back(now->val);
        if (now->right) dfs(now->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        dfs(root);
        for (int i = 1; i < seq.size(); ++i) if (seq[i - 1] >= seq[i]) return false;
        return true;
    }
};
    \end{lstlisting}

    \subsubsection{二叉搜索树的最小绝对差}

    \href{https://leetcode.cn/problems/minimum-absolute-difference-in-bst/}{二叉搜索树的最小绝对差}

    用中序遍历序列求解：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<int> seq;
    void dfs(TreeNode* now) {
        if (now->left) dfs(now->left);
        this->seq.emplace_back(now->val);
        if (now->right) dfs(now->right);
    }
public:
    int getMinimumDifference(TreeNode *root) {
        dfs(root);
        int ans = INT_MAX;
        for (int i = 1; i < seq.size(); ++i) ans = min(ans, seq[i] - seq[i - 1]);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{二叉搜索树中的众数}

    \href{https://leetcode.cn/problems/find-mode-in-binary-search-tree/}{二叉搜索树中的众数}

    利用二叉搜索树中序遍历序列有序的特点，使用pre指针和now指针，在中序遍历时寻找更新答案：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int max_cnt = 0, cnt = 0;
    TreeNode* pre = nullptr;
    vector<int> res;

    void solve(TreeNode* now) {
        if (!now) return;
        solve(now->left); // 左

        if (!pre) cnt = 1; // 更新计数
        else if (pre->val == now->val) ++cnt;
        else if (pre->val != now->val) cnt = 1;

        pre = now;  // 中序遍历回溯时的上一个节点
        if (cnt > max_cnt) res.clear(), max_cnt = cnt, res.emplace_back(now->val);
        else if (cnt == max_cnt) res.emplace_back(now->val); // 中序遍历，操作当前节点

        solve(now->right); // 右
    }
public:
    vector<int> findMode(TreeNode* root) {
        solve(root);
        return res;
    }
};
    \end{lstlisting}

    \subsubsection{二叉树的最近公共祖先}

    \href{https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/}{二叉树的最近公共祖先}

    Least Common Ancestors，LCA，最近公共祖先。

    我们需要在从下到上的寻找最近公共祖先，而后序遍历的回溯过程，满足这一要求。

    所以使用后序遍历解决这个问题，由于只有一对查询，所以时间复杂度为 $ \Theta(N) $ ，n为节点个数。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q || root == nullptr) return root; // 找到了p或者q，或者没找到

        auto l = lowestCommonAncestor(root->left, p, q);
        auto r = lowestCommonAncestor(root->right, p, q);  // 后序遍历，寻找左子树和右子树中有没有出现p和q

        if (l && r) return root;  // 分别在左子树和右子树中找到了，所以当前根节点是LCA
        else if (l && !r) return l;  // 在左子树中找到了，返回结果
        else if (!l && r) return r;  // 在右子树中找到了，返回结果
        else return nullptr; 
    }
};
    \end{lstlisting}

    树上倍增法、Tarjan算法，暂且略过。

    \subsubsection{二叉搜索树的最近公共祖先}

    \href{https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/}{二叉搜索树的最近公共祖先}

    由于是二叉搜索树，所以，找到第一个大于p小于q的节点，就是p和q的LCA。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val > q->val) swap(p, q);

        if (p->val <= root->val && root->val <= q->val) return root;
        if (root->val < p->val) return lowestCommonAncestor(root->right, p, q);
        if (root->val > q->val) return lowestCommonAncestor(root->left, p, q);
        return nullptr;
    }
};
    \end{lstlisting}

    \subsubsection{二叉搜索树中的插入操作}

    \href{https://leetcode.cn/problems/insert-into-a-binary-search-tree/}{二叉搜索树中的插入操作}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        auto res = root;
        
        while (root) {
            if (!root->left && root->val > val) {
                root->left = new TreeNode(val);
                return res;
            } else if (!root->right && root->val < val) {
                root->right = new TreeNode(val);
                return res;
            } else {
                if (root->val > val) root = root->left;
                else root = root->right;
            }
        }
        return res;
    }
};
    \end{lstlisting}

    \subsubsection{删除二叉搜索树中的节点}

    \href{https://leetcode.cn/problems/delete-node-in-a-bst/}{删除二叉搜索树中的节点}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) {
            return nullptr;
        } else if (root->val > key) {
            root->left = deleteNode(root->left, key);
            return root;
        } else if (root->val < key) {
            root->right = deleteNode(root->right, key);
            return root;
        } else {
            if (!root->left && !root->right) {  // 左子树和右子树都为空
                delete root;
                return nullptr;
            } else if (!root->left) {  // 只有右子树
                auto res = root->right;
                delete root;
                return res;
            } else if (!root->right) {  // 只有左子树
                auto res = root->left;
                delete root;
                return res;
            } else {  // 左子树，右子树，都存在
                auto l = root->left;
                auto r = root->right;
                auto concat = root->right;
                delete root;
                while (concat->left) concat = concat->left;  //  左子树接到右子树的左边

                concat->left = l;
                return r;
            }
        }
    }
};
    \end{lstlisting}

    \subsubsection{修剪二叉搜索树}

    \href{https://leetcode.cn/problems/trim-a-binary-search-tree/}{修剪二叉搜索树}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root) {
            return nullptr;
        } else if (root->val < low) {  // 当前节点和左子树都不能要了
            return trimBST(root->right, low, high);
        } else if (root->val > high) {  // 当前节点和右子树都不能要了
            return trimBST(root->left, low, high);
        } else {
            root->left = trimBST(root->left, low, high);  // 递归修剪左右子树
            root->right = trimBST(root->right, low, high);
            return root;
        }
    }
};
    \end{lstlisting}

    \subsubsection{将有序数组转换为二叉搜索树}

    \href{https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/}{将有序数组转换为二叉搜索树}

    需要生成一棵高度平衡的二叉搜索树。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;

        int mid = nums.size() / 2;
        auto root = new TreeNode(nums[mid]);

        vector<int> l(nums.begin(), nums.begin() + mid);
        vector<int> r(nums.begin() + mid + 1, nums.end());

        root->left = sortedArrayToBST(l);
        root->right = sortedArrayToBST(r);
        return root;
    }
};
    \end{lstlisting}

    \subsubsection{把二叉搜索树转换为累加树}

    \href{https://leetcode.cn/problems/convert-bst-to-greater-tree/}{把二叉搜索树转换为累加树}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int s = 0;
    void dfs(TreeNode* now) {
        if (!now) return;
        dfs(now->right);
        now->val += s;
        s = now->val;
        dfs(now->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }
};
    \end{lstlisting}

    \subsection{回溯算法}

    \subsubsection{组合}

    \href{https://leetcode.cn/problems/combinations/}{组合}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> res;
        dfs(ans, res, 0, n, k);
        return ans;
    }
    void dfs(vector<vector<int>>& ans, vector<int>& res, int last, int max, int level) {
        if (level <= 0) {
            ans.emplace_back(res);
            return;
        }
        for (int i = last + 1; i <= max; ++i) {
            res.emplace_back(i);
            dfs(ans, res, i, max, level - 1);
            res.pop_back();
        }
    }
};
    \end{lstlisting}

    \subsubsection{组合总和III}

    \href{https://leetcode.cn/problems/combination-sum-iii/}{组合总和III}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> res;
        solve(ans, res, k, n, 1);
        return ans;
    }

    void solve(vector<vector<int>>& ans, vector<int>& res, int depth, int remain, int last) {
        if (depth == 0 && remain == 0) {
            ans.emplace_back(res);
            return;
        } else if (depth == 0 || remain <= 0) {
            return;
        } else {
            for (int i = last; i <= 9; ++i) {
                if (remain - i < 0) continue;
                res.emplace_back(i);
                solve(ans, res, depth - 1, remain - i, i + 1);
                res.pop_back();
            }
        }
    }
};
    \end{lstlisting}

    \subsubsection{电话号码的字母组合}

    \href{https://leetcode.cn/problems/letter-combinations-of-a-phone-number/}{电话号码的字母组合}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<string> ans;
    string res;
    unordered_map<char, string> db;

    void solve(const string& digits, int pos) {
        if (pos >= digits.size() && digits.size()) {
            ans.emplace_back(res);
            return;
        }

        for (const char& c : db[digits[pos]]) {
            res += c;
            solve(digits, pos + 1);
            res.pop_back();
        }
    }

public:
    vector<string> letterCombinations(string digits) {
        db['2'] = "abc";
        db['3'] = "def";
        db['4'] = "ghi";
        db['5'] = "jkl";
        db['6'] = "mno";
        db['7'] = "pqrs";
        db['8'] = "tuv";
        db['9'] = "wxyz";
        solve(digits, 0);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{总和组合}

    \href{https://leetcode.cn/problems/combination-sum/}{总和组合}

    每个数字可以用任意次数。

    \begin{lstlisting}[language=C++, lineskip=3pt]
// Template
class Solution {
private:
    vector<vector<int>> ans;
    vector<int> res;
    void solve(const vector<int>& nums, int idx, int s, const int& val) {
        if (s == val) {
            ans.emplace_back(res);
            return;
        }

        for (int i = idx; i < nums.size(); ++i) {
            if (nums[i] + s > val) break;  // 为了实现这个剪枝，需要提前排序nums
            res.emplace_back(nums[i]);
            solve(nums, i, s + nums[i], val);  // 这里idx = i，实现重复选
            res.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        solve(candidates, 0, 0, target);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{组合总和 II}

    \href{https://leetcode.cn/problems/combination-sum-ii/}{组合总和 II}

    候选数组中出现的每一个数字只能用一次，但是候选数组中会有重复的数字，结果不允许有重复。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
    vector<int> res;
    vector<vector<int>> ans;
    unordered_map<int, int> total, used;
    void solve(const vector<int>& candi, int idx, int s, const int& target) {
        if (s == target) {
            ans.emplace_back(res);
            return;
        }

        for (int i = idx; i < candi.size(); ++i) {
            if (used[candi[i]] == total[candi[i]]) continue;  // 使用个数计数
            if (s + candi[i] > target) break;

            used[candi[i]] += 1;
            res.emplace_back(candi[i]);
            solve(candi, i, s + candi[i], target);  // 因为可能重复使用，所以是i不是i + 1
            res.pop_back();
            used[candi[i]] -= 1;
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        for (const int& i : candidates) ++total[i], used[i] = 0;  // 给每个数字计数
        sort(candidates.begin(), candidates.end());  // 排序并去重
        candidates.resize(unique(candidates.begin(), candidates.end()) - candidates.begin());

        solve(candidates, 0, 0, target);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{分割回文串}

    \href{https://leetcode.cn/problems/palindrome-partitioning/}{分割回文串}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<vector<int>> f;
    vector<vector<string>> ret;
    vector<string> ans;
    int n;
public:
    void dfs(const string& s, int i) {
        if (i == n) {
            ret.push_back(ans);
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                ans.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<int>(n, true));

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }
};
    \end{lstlisting}

    \subsubsection{复原IP地址}

    \href{https://leetcode.cn/problems/restore-ip-addresses/}{复原IP地址}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// Template
class Solution {
private:
    bool valid(const string& s, int l, int r) {
        if (r - l + 1 > 3) return false;
        if (l > r) return false;
        if (s[l] == '0' && l != r) return false;

        int a = 0;
        for (int i = l; i <= r; ++i) {
            a *= 10;
            a += s[i] - '0';
        }
        return 0 <= a && a <= 255;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        const int n = s.size();

        vector<string> ans;
        if (n < 4) return ans;

        for (int i = 0; i <= 2; ++i) {
            if (!valid(s, 0, i)) continue;
            for (int j = i + 1; j <= i + 3; ++j) {
                if (!valid(s, i + 1, j)) continue;
                for (int k = j + 1; k <= j + 3; ++k) {
                    if (!valid(s, j + 1, k)) continue;
                    if (!valid(s, k + 1, n - 1)) continue;
                    // [0, i]
                    // [i + 1, j]
                    // [j + 1, k]
                    // [k + 1, n - 1]
                    string res;
                    res += s.substr(0, i + 1) + '.';
                    res += s.substr(i + 1, j - i) + '.';
                    res += s.substr(j + 1, k - j) + '.';
                    res += s.substr(k + 1, n - k - 1);
                    ans.emplace_back(res);
                    cerr << res << endl;
                }
            }
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{子集}

    \href{https://leetcode.cn/problems/subsets/}{子集}

    \textbf{写法1：}一共有 $ 2^n $ 个结果，下面的代码对每个结果需要 $ \Theta(n) $ 的时间来枚举，因此时间复杂度为 $ \Theta(n2^n) $ （不考虑复制vector的时间）。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<int> res;
    vector<vector<int>> ans;
    void solve(const vector<int>& arr, int idx) {
        if (idx >= arr.size()) {
            ans.emplace_back(res);
            return;
        } else {
            solve(arr, idx + 1);
            res.emplace_back(arr[idx]);
            solve(arr, idx + 1);
            res.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        solve(nums, 0);
        return ans;
    }
};
    \end{lstlisting}

    \textbf{写法2：}下面的代码，每次进入递归函数，都能生成一个结果，同时递归函数中存在一个for循环，因此时间复杂度为 $ \Theta(n2^n) $ （不考虑复制vector的时间）。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<int> res;
    vector<vector<int>> ans;
    void solve(const vector<int>& arr, int idx) {
        ans.emplace_back(res);
        if (idx >= arr.size()) return;
        for (int i = idx; i < arr.size(); ++i) {
            res.emplace_back(arr[i]);
            solve(arr, i  +1);
            res.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        solve(nums, 0);
        return ans;
    }
};
    \end{lstlisting}

    \textbf{写法3：}二进制状态枚举。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<int> res;
    vector<vector<int>> ans;
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        const int n = nums.size();
        const int cnt = 0x01 << n;

        for (int i = 0; i < cnt; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((0x01 << j) & i) res.emplace_back(nums[j]);
            }
            ans.emplace_back(res);
            res.clear();
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{子集 II}

    \href{https://leetcode.cn/problems/subsets-ii/}{子集 II}
    
    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    unordered_map<int, int> total;
    vector<vector<int>> ans;
    vector<int> res;
    void solve(const vector<int>& arr, int idx) {
        if (idx >= arr.size()) {
            ans.emplace_back(res);
        } else {
            solve(arr, idx + 1);
            for (int i = 0; i < total[arr[idx]]; ++i) {
                res.emplace_back(arr[idx]);
                solve(arr, idx + 1);
            }
            for (int i = 0; i < total[arr[idx]]; ++i) res.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (auto& i : nums) total[i]++;
        const int n = int(unique(nums.begin(), nums.end()) - nums.begin());
        nums.resize(n);
        solve(nums, 0);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{递增子序列}

    \href{https://leetcode.cn/problems/non-decreasing-subsequences/}{递增子序列}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<vector<int>> ans;
    vector<int> res;
    void solve(const vector<int>& arr, int idx) {
        if (res.size() >= 2) ans.emplace_back(res);  // 每个有效的子序列都加入答案
        if (idx >= arr.size()) return;

        unordered_set<int> used;  // 当前“层”去重
        for (int i = idx; i < arr.size(); ++i) {
            if (used.count(arr[i]) > 0) continue;
            if (!res.empty() && res.back() > arr[i]) continue;
            
            used.insert(arr[i]);
            res.emplace_back(arr[i]);
            solve(arr, i + 1);
            res.pop_back();

        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        solve(nums, 0);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{全排列}

    \href{https://leetcode.cn/problems/permutations/}{全排列}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
    vector<bool> used;
    vector<vector<int>> ans;
    vector<int> res;
    void solve(const vector<int>& arr) {
        if (res.size() == arr.size()) {
            ans.emplace_back(res);
            return;
        } else {
            for (int i = 0; i < arr.size(); ++i) {
                if (!used[i]) {  // 选择每一个位置上的元素
                    used[i] = true;
                    res.emplace_back(arr[i]);
                    solve(arr);
                    res.pop_back();
                    used[i] = false;
                }
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        used.resize(nums.size());
        solve(nums);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{全排列 II}

    \href{https://leetcode.cn/problems/permutations-ii/}{全排列 II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    vector<int> res;
    vector<bool> used;
    vector<vector<int>> ans;
    void solve(const vector<int>& arr) {
        if (res.size() == arr.size()) {
            ans.emplace_back(res);
        } else {
            unordered_set<int> st;
            for (int i = 0; i < arr.size(); ++i) {
                if (used[i]) continue;
                if (st.count(arr[i]) != 0) continue;

                st.insert(arr[i]);
                used[i] = true;
                res.emplace_back(arr[i]);
                solve(arr);
                res.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        used.resize(nums.size());
        solve(nums);
        return ans;
    }
};
    \end{lstlisting}

    原来2020年的时候，我还有本事写出下面这样的代码：    

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    void solve(vector<vector<int>>& ans, vector<int> nums, int index) {
        if (index + 1 >= nums.size()) {
            ans.emplace_back(nums);
            return;
        }

        for (int i = index; i < nums.size(); ++i) {
            if (i != index and nums[i] == nums[index]) continue;
            swap(nums[i], nums[index]);
            solve(ans, nums, index + 1);
        }
    }

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        solve(ans, nums, 0);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{重新安排行程}

    \href{https://leetcode.cn/problems/reconstruct-itinerary/}{重新安排行程}

    大模拟，大暴力，

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
    vector<bool> used;
    vector<string> ans, res;
    map<string, vector<pair<string, int>>> graph;

    void solve(const vector<vector<string>>& t) {
        if (res.size() == t.size() + 1) {
            ans = res;  // 字典序最小的可行解
            return;
        } else {
            auto& from = res.back();
            for (auto& p : graph[from]) {
                auto& to = p.first;
                auto& idx = p.second;
                if (!ans.empty()) break;
                if (used[idx]) continue;

                used[idx] = true;
                res.emplace_back(to);
                solve(t);
                res.pop_back();
                used[idx] = false;
            }
        }
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        res.emplace_back("JFK");  // 临时结果
        used.resize(tickets.size());  // 没一张票用过没

        for (int i = 0; i < tickets.size(); ++i) {
            auto& from = tickets[i][0];
            auto& to = tickets[i][1];
            graph[from].emplace_back(make_pair(to, i));  // 每一个from的to的列表，并用pair记录在tickets中的下标，用于标记票被使用
        }
        for (auto& p : graph) {
            sort(p.second.begin(), p.second.end(), [](auto a, auto b){  // 排序每个from的to列表，满足字典序最小的要求
                return a.first < b.first;
            });
        }
        solve(tickets);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{N皇后}

    \href{https://leetcode.cn/problems/n-queens/}{N皇后}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
    vector<bool> col_used;
    vector<string> res;
    vector<vector<string>> ans;

    inline bool valid45(int row, int col) {
        while (row >= 0 && col >= 0) {
            if (res[row][col] == 'Q') return false;
            --row;
            --col;
        }
        return true;
    }

    inline bool valid135(int row, int col, int n) {
        while (row >= 0 && col < n) {
            if (res[row][col] == 'Q') return false;
            --row;
            ++col;
        }
        return true;
    }

    void solve(int row, int n) {
        if (row == n) {
            ans.emplace_back(res);
        } else {
            for (int col = 0; col < n; ++col) {
                if (col_used[col]) continue;
                if (valid45(row, col) && valid135(row, col, n)) {
                    col_used[col] = true;
                    res[row][col] = 'Q';
                    solve(row + 1, n);
                    res[row][col] = '.';
                    col_used[col] = false;
                }
            }
        }
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        col_used.resize(n ,false);
        for (int i = 0; i < n; ++i) res.emplace_back(n, '.');

        solve(0, n);
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{解数独}

    \href{https://leetcode.cn/problems/sudoku-solver/}{解数独}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }

    bool legal(vector<vector<char>>& board, int x, int y, char c) {
        for (int i = 0; i < 9; ++i) if (board[x][i] == c || board[i][y] == c) return false;

        int delta_x = x / 3;
        int delta_y = y / 3;

        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                if (board[i + delta_x * 3][j + delta_y * 3] == c) return false;
        return true;
    }

    bool solve(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    for (int k = 1; k <= 9; ++k) {
                        if (legal(board, i, j, char('0' + k))) {
                            board[i][j] = char('0' + k);
                            if (solve(board)) return true;
                            else board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};
    \end{lstlisting}

    \subsection{贪心算法}

    \subsubsection{分发饼干}

    \href{https://leetcode.cn/problems/assign-cookies/}{分发饼干}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        
        int ans = 0, idx_g = 0, idx_s = 0;
        while (idx_g < g.size() && idx_s < s.size()) {
            if (g[idx_g] <= s[idx_s]) {
                ++ans;
                ++idx_g;
                ++idx_s;
            } else {
                ++idx_s;
            }
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{摆动序列}

    \href{https://leetcode.cn/problems/wiggle-subsequence/}{摆动序列}

    贪心做法：计算局部最大值最小值的个数，$ \Theta(n) $

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return (int)nums.size();
        int ans = 1, last_diff = 0, now_diff = 0;

        for (int i = 0; i < nums.size() - 1; ++i) {
            now_diff = nums[i + 1] - nums[i];
            if ((now_diff < 0 && last_diff >= 0) || (now_diff > 0 && last_diff <= 0)) {
                last_diff = now_diff;
                ++ans;
            }
        }
        return ans;
    }
};
    \end{lstlisting}

    动态规划做法，$ \Theta(n^2) $（可以用数据结构优化成$ \Theta(n \log n) $）

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[1005][2] = {};
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return (int)nums.size();

        // dp[i][0]表示以i结尾，上一个差值为负的子序列的最大长度，
        // dp[i][1]表示以i结尾，上一个差值为正的子序列的最大长度，
        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.size(); ++i) {
            dp[i][0] = dp[i][1] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
                if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
            }
        }
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};
    \end{lstlisting}

    \subsubsection{最大子数组和}

    \href{https://leetcode.cn/problems/maximum-subarray/}{最大子数组和}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int now = 0;
        for (int i : nums) {
            if (now > 0) {
                now += i;
            } else {
                now = i;
            }
            ans = max(ans, now);
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{买卖股票的最佳时机 II}

    \href{https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/}{买卖股票的最佳时机 II}

    贪心做法，每天的利润加起来，就是最大的总和利润。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for (int i = 1; i < prices.size(); ++i) ans += max(prices[i] - prices[i - 1], 0);
        return ans;
    }
};
    \end{lstlisting}

    动态规划做法。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() < 2) return 0;

        vector<int[2]> dp(prices.size());
        dp[0][0] = 0;           // 第i天，不持有股票的最大利润
        dp[0][1] = -prices[0];  // 第i天，持有股票的最大利润

        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return dp[prices.size() - 1][0];
    }
};
    \end{lstlisting}

    \subsubsection{跳跃游戏}

    \href{https://leetcode.cn/problems/jump-game/}{跳跃游戏}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (ans < i) return false;
            if (ans >= nums.size() - 1) return true;
            ans = max(i + nums[i], ans);
        }
        return true;
    }
};
    \end{lstlisting}

    \subsubsection{跳跃游戏 II}

    \href{https://leetcode.cn/problems/jump-game-ii/}{跳跃游戏 II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int jump(vector<int>& nums) {
        // current_step 表示走了ans步能达到的最远位置，next_step 表示走ans + 1步能达到的最远位置
        int ans = 0, current_step = 0, next_step = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {  // i < nums.size() - 1
            next_step = max(next_step, nums[i] + i);
            if (current_step == i) {
                ++ans;
                current_step = next_step;
            }
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{K次取反后的最大化数组和}

    \href{https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/}{K次取反后的最大化数组和}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() && k > 0 && nums[i] <= 0; ++i, --k) nums[i] *= -1;
        int ans = 0, m = INT_MAX;
        for (int i = 0; i < nums.size(); ++i) ans += nums[i], m = min(m, nums[i]);

        if (k % 2 == 1) return ans - 2 * m;
        else return ans;
    }
};
    \end{lstlisting}

    \subsubsection{加油站}

    \href{https://leetcode.cn/problems/gas-station/}{加油站}

    如果now left小于0，说明从之前的一段出发都是不可行的，要从i+1重新开始尝试。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int ans = 0, total_left = 0, now_left = 0;
        
        for (int i = 0; i < gas.size(); ++i) {
            now_left += gas[i] - cost[i];
            total_left += gas[i] - cost[i];
            if (now_left < 0) {
                now_left = 0;
                ans = i + 1;
            }
        }
        
        if (total_left < 0) return -1;
        else return ans;
    }
};
    \end{lstlisting}

    \subsubsection{分发糖果}

    \href{https://leetcode.cn/problems/candy/}{分发糖果}

    前后两次遍历，确定结果，

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> cnt(ratings.size(), 1);

        for (int i = 1; i < ratings.size(); ++i)  // 从前往后
            if (ratings[i - 1] < ratings[i])
                cnt[i] = cnt[i - 1] + 1;

        for (int i = ratings.size() - 2; i >= 0; --i)  // 从后往前
            if (ratings[i] > ratings[i + 1])
                cnt[i] = max(cnt[i], cnt[i + 1] + 1);
        
        int ans = 0;
        for (auto& i : cnt) ans += i;
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{柠檬水找零}

    \href{https://leetcode.cn/problems/lemonade-change/}{柠檬水找零}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int cnt_5 = 0, cnt_10 = 0;
        for (int i : bills) {
            if (i == 5) {
                ++cnt_5;
            } else if (i == 10) {
                ++cnt_10;
                if (cnt_5 > 0) --cnt_5;
                else return false;
            } else if (i == 20) {
                if (cnt_5 > 0 and cnt_10 > 0) {
                    --cnt_5;
                    --cnt_10;
                } else if (cnt_5 >= 3) {
                    cnt_5 -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};
    \end{lstlisting}

    \subsubsection{根据身高重建队列}

    \href{https://leetcode.cn/problems/queue-reconstruction-by-height/}{根据身高重建队列}

    先对身高从高到低排序，然后一次插入相应位置。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) -> bool {
            if (a[0] == b[0]) return a[1] < b[1];
            else return a[0] > b[0];
        });

        vector<vector<int>> ans;
        for (vector<int>& now : people) {
            if (ans.size() <= now[1]) {
                ans.emplace_back(now);
            } else {
                ans.insert(ans.begin() + now[1], now);
            }
        }
        
        return ans;
    }
};
    \end{lstlisting}
    
    \subsubsection{用最少数量的箭引爆气球}

    \href{https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/}{用最少数量的箭引爆气球}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](auto& a, auto& b){
            if (a[1] == b[1]) return a[0] < b[0];
            else return a[1] < b[1];
        });

        int now_pos = points[0][1], ans = 1;
        for (int i = 1; i < points.size(); ++i) {
            if (now_pos < points[i][0]) {
                now_pos = points[i][1];
                ++ans;
            }
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{无重叠区间}

    \href{https://leetcode.cn/problems/non-overlapping-intervals/}{无重叠区间}

    先按照右边界排序，排序之后，用贪心计算不重叠区间的个数，然后计算需要删除的区间的个数。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
            if (a[1] == b[1]) return a[0] < b[0];
            else return a[1] < b[1];
        });

        int ans = 1, now_end = intervals[0][1];
        for (int i = 1; i < intervals.size(); ++i) {
            if (now_end <= intervals[i][0]) {
                ++ans;
                now_end = intervals[i][1];
            }
        }
        
        return (int)intervals.size() - ans;
    }
};
    \end{lstlisting}

    \subsubsection{划分字母区间}

    \href{https://leetcode.cn/problems/partition-labels/}{划分字母区间}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> partitionLabels(string s) {
        const int n = s.size();
        int last_pos_all[26] = {};  // s中，每个字母最后一次出现的位置
        for (int i = 0; i < n; ++i) last_pos_all[s[i] - 'a'] = i;

        int last_pos = 0, cnt = 0;
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            ++cnt;
            last_pos = max(last_pos, last_pos_all[s[i] - 'a']);  // 如果遍历到当前，遍历过的所有字母出现的最大位置 == i，说明已经找到了一个满足题目要求的子串
            if (last_pos == i) {
                ans.emplace_back(cnt);
                cnt = 0;
            }
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{合并区间}

    \href{https://leetcode.cn/problems/merge-intervals/}{合并区间}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 本题需要按照区间的左边界排序
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {return a[0] < b[0];});

        vector<vector<int>> ans;
        int l = intervals[0][0], r = intervals[0][1];
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] <= r) {
                r = max(r, intervals[i][1]);
            } else {
                ans.emplace_back(vector<int>{ l, r });
                l = intervals[i][0];
                r = intervals[i][1];
            }
        }
        ans.emplace_back(vector<int>{ l, r });
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{单调递增的数字}

    \href{https://leetcode.cn/problems/monotone-increasing-digits/}{单调递增的数字}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int pos = 1;  // 寻找第一个 s[pos - 1] > s[pos]的位置
        while (pos < s.size() && s[pos - 1] <= s[pos]) ++pos;

        if (pos == s.size()) return stoi(s); // n本身就满足非降序的要求，直接返回

        while (pos > 0 && s[pos - 1] > s[pos]) {
            s[pos - 1] -= 1; // 为了满足题目不大于n的要求，pos - 1 位置的数字需要 -1
            --pos;  // 同时为了满足非降序序列的要求，如果s[pos - 1] -= 1后，s[pos - 2] > s[pos - 1]了，还需要继续往下-1
        }

        pos += 1;  // 移动指针到最后一个 -1 的数字之前
        while (pos < s.length()) {
            s[pos] = '9';
            ++pos;  // 为了满足题目最大答案的要求，后面的数字全部填成9
        }
        return stoi(s);
    }
};
    \end{lstlisting}

    \subsubsection{卖卖股票的最佳时机，含手续费}

    \href{https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/}{卖卖股票的最佳时机，含手续费}

    多了一笔手续费，手续费是固定值，每个买入卖出的完整过程需要交手续费。

    贪心的解法：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int ans = 0, min_price = prices[0];

        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] < min_price) {
                min_price = prices[i];  // 股票还在降价
            } else if (prices[i] >= min_price && prices[i] <= min_price + fee) {
                continue;  // 还不能盈利
            } else {
                ans += prices[i] - min_price - fee; // 盈利
                min_price = prices[i] - fee;  // 考虑继续持有还能盈利的情况，更新min_price的时候减掉fee
            }
        }
        
        return ans;
    }
};
    \end{lstlisting}

    动态规划的解法：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[50000 + 5][2] = {};  // 空间其实可以优化，因为只依赖前一个状态
public:
    int maxProfit(vector<int>& prices, int fee) {
        dp[0][0] = 0;  // 第 i 天，不持有股票的盈利
        dp[0][1] = -prices[0];  // 第 i 天，持有股票的盈利（交易费用放到抛出时计算）

        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);  // 第 i 天，继续不持有，还是当天抛出
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);        // 第 i 天，继续持有，还是当天买入
        }

        return dp[prices.size() - 1][0];
    }
};
    \end{lstlisting}

    \subsubsection{监控二叉树}

    \href{https://leetcode.cn/problems/binary-tree-cameras/}{监控二叉树}

    思路：先在叶子节点的父节点上放摄像头，然后向上遍历，隔一个节点放一个，这样做所需摄像头个数最少。

    将二叉树中的节点分为三种状态：

    \begin{itemize}
        \item 0，该节点没有被摄像头覆盖
        \item 1，该节点有一个摄像头
        \item 2，该节点被相邻节点的摄像头覆盖（同时将空节点归入这个状态）
    \end{itemize}

    如果左右子节点都有覆盖（2），则当前节点无覆盖（0）；

    如果左右子节点存在一个无覆盖（0），则当前节点需要放一个摄像头（1）；

    如果左右节点存在一个摄像头（1），则当前节点被覆盖（2）；

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int ans = 0;
    int solve(TreeNode* now) {
        if (!now) return 2;

        int l_state = solve(now->left);
        int r_state = solve(now->right);

        if (l_state == 2 && r_state == 2) {
            return 0;
        } else if (l_state == 0 || r_state == 0) {
            ++ans;
            return 1;
        } else if (l_state == 1 || r_state == 1) {
            return 2;
        } else {
            return -1;
        }
    }
public:
    int minCameraCover(TreeNode* root) {
        if (solve(root) == 0) ++ans;
        return ans;
    }
};
    \end{lstlisting}

    \subsection{动态规划（Dynamic Programming，DP）}

    贪心从局部最优推导到全局最优，而动态规划从上一个状态推导下一个状态。

    \begin{itemize}
        \item 确定DP数组，以及数组下标对应的含义；
        \item 确定递推公式；
        \item 确定DP数组初始化的方式；
        \item 确定遍历的顺序；
        \item 开始推导DP数组；
    \end{itemize}

    \subsubsection{斐波那契数}

    \href{https://leetcode.cn/problems/fibonacci-number/}{斐波那契数}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        
        int a = 0;
        int b = 1;
        
        for (int i = 2; i <= N; ++i) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};
    \end{lstlisting}

    \subsubsection{爬楼梯}

    \href{https://leetcode.cn/problems/climbing-stairs/}{爬楼梯}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        int a = 1, b = 2, c;
        for (int i = 3; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }

        return b;
    }
};
    \end{lstlisting}

    \subsubsection{使用最小花费爬楼梯}

    \href{https://leetcode.cn/problems/min-cost-climbing-stairs/}{使用最小花费爬楼梯}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int minCostClimbingStairs(vector<int> &cost) {
        vector<int> total_cost(cost.size() + 1);
        for (int i = 2; i < total_cost.size(); ++i) {
            total_cost[i] = min(total_cost[i - 1] + cost[i - 1], total_cost[i - 2] + cost[i - 2]);
        }
        return total_cost.back();
    }
};
    \end{lstlisting}

    \subsubsection{不同路径}

    \href{https://leetcode.cn/problems/unique-paths/}{不同路径}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[105][105] = {};
public:
    int uniquePaths(int m, int n) {
        dp[0][1] = 1;
        for (int i = 1; i <= m; ++i) 
            for (int j = 1; j <= n; ++j)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m][n];
    }
};
    \end{lstlisting}

    \subsubsection{不同路径II}

    \href{https://leetcode.cn/problems/unique-paths-ii/}{不同路径II}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[105][105] = {};
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        const int n = obstacleGrid.size();
        const int m = obstacleGrid[0].size();
        dp[0][1] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (obstacleGrid[i - 1][j - 1] == 1) dp[i][j] = 0;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n][m];
    }
};
    \end{lstlisting}

    \subsubsection{整数拆分}

    \href{https://leetcode.cn/problems/integer-break/}{整数拆分}

    令 $ dp[n] $ 表示n的整数拆分的结果，现在，将n拆分为m和n - m，则要么，$ dp[n] = m \times (n - m) $ ，要么，$ dp[n] = m \times dp[n - m] $ ，所以，该问题的递推公式为 $ dp[n] = \max_{1 \le m \le n - 1} (m \times (n - m), m \times dp[n - m]) $ 。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[60];
public:
    int integerBreak(int n) {
        dp[2] = 1;
        dp[3] = 2;
        for (int i = 4; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};
    \end{lstlisting}

    \subsubsection{不同的二叉搜索树}

    \href{https://leetcode.cn/problems/unique-binary-search-trees/}{不同的二叉搜索树}

    令 $ dp[n] $ 表示由1到n组成的不同的二叉搜索树的个数，令 $ 1 \le m \le n $ ，将m作为二叉搜索树的根节点，1到m-1组成左子树，m+1到n组成右子树，则左子树有 $ dp[m - 1] $ 种情况，右子树有 $ dp[n - m] $ 种情况，一共有 $ dp[m - 1] \times dp[n - m] $ 种情况，所以，递推公式为：$ dp[n] = \sum_{1 \le m \le n} dp[m - 1] \times dp[n - m] $ 。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[20] = {};
public:
    int numTrees(int n) {
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};
    \end{lstlisting}

    \subsubsection{01背包问题}

    二维数组的写法：

    \begin{lstlisting}[language=C++, lineskip=3pt]
void test_2_wei_bag_problem1() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagweight = 4;

    // 二维数组
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));

    // 初始化
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }

    cout << dp[weight.size() - 1][bagweight] << endl;
}
    \end{lstlisting}

    滚动数组的写法（注意遍历背包容量的顺序）：

    \begin{lstlisting}[language=C++, lineskip=3pt]
void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
    \end{lstlisting}

    \subsubsection{分割等和子集}

    \href{https://leetcode.cn/problems/partition-equal-subset-sum/}{分割等和子集}

    使用01背包的思想；

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution1 {
public:
    bool canPartition(vector<int>& nums) {
        const int n = nums.size();
        int total = 0, target;

        if (n < 2) return false;
        for (auto& i : nums) total += i;
        if (total % 2 == 1) return false;

        target = total / 2;
        vector<bool> dp(target + 1); dp[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = target; j >= nums[i]; --j) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

class Solution2 {
public:
    bool canPartition(vector<int>& nums) {
        const int n = nums.size();
        int total = 0, target;

        if (n < 2) return false;
        for (auto& i : nums) total += i;
        if (total % 2 == 1) return false;

        target = total / 2;
        vector<int> dp(target + 1);
        for (int i = 0; i < n; ++i) {
            for (int j = target; j >= nums[i]; --j) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
                if (dp[j] == target) return true;
            }
        }
        return false;
    }
};
    \end{lstlisting}

    \subsubsection{最后一块石头的重量 II}

    \href{https://leetcode.cn/problems/last-stone-weight-ii/}{最后一块石头的重量 II}

    01背包原理，令所有石头的总重为total，则该问题相当于，每块石头的重量为i，同时价值也为i，背包容量为 $ \lfloor total / 2 \rfloor $ ，最后的答案是 $ total - 2 \times dp[\lfloor total / 2 \rfloor] $ 。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[3000 + 5] = {};
public:
    int lastStoneWeightII(vector<int>& stones) {
        int total = 0;
        const int n = stones.size();
        for (auto& i : stones) total += i;
        int target = total / 2;
        
        for (auto& i : stones) {
            for (int j = target; j >= i; --j) {
                dp[j] = max(dp[j], dp[j - i] + i);
            }
        }
        
        return total - 2 * dp[target];
    }
};
    \end{lstlisting}

    \subsubsection{目标和}

    \href{https://leetcode.cn/problems/target-sum/}{目标和}

    令数组中所有整数的和为total，本题目的目标可以转化为，从数组中选择出一些整数，使它们的和为 $ (total + target) / 2 $ ，这样的选择总数有多少，于是乎可以转化为01背包问题。
    
    初始状态 $ dp[0] = 1 $ ，状态转移 $ dp[j] += dp[j - arr[i]] $ 。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[1005] = {};
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int total = 0;
        for (auto& i : nums) total += i;

        if (target > total || target < -total) return 0;
        if ((total + target) % 2 == 1) return false;

        dp[0] = 1;
        int volume = (total + target) / 2;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = volume; j >= nums[i]; --j) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[volume];
    }
};
    \end{lstlisting}

    \subsubsection{一和零}

    \href{https://leetcode.cn/problems/ones-and-zeroes/}{一和零}

    依旧可以看作01背包，只不过每件物品现在有两种容量。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[105][105] = {};
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        for (int i = 0; i < strs.size(); ++i) {
            int one_cnt = 0, zero_cnt = 0;
            for (const char& c : strs[i]) {
                if (c == '1') ++one_cnt;
                else ++zero_cnt;
            }

            for (int j = n; j >= one_cnt; --j) {
                for (int k = m; k >= zero_cnt; --k) {
                    dp[j][k] = max(dp[j][k], dp[j - one_cnt][k - zero_cnt] + 1);
                }
            }
        }

        return dp[n][m];
    }
};
    \end{lstlisting}

    \subsubsection{零钱兑换 II}

    \href{https://leetcode.cn/problems/coin-change-ii/}{零钱兑换 II}

    完全背包裸题，和01背包的区别在于，在使用滚动数组的写法时，完全背包的第二层循环从小到大遍历（因为可以不限次数重复使用）。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[5005] = {1, };
public:
    int change(int amount, vector<int>& coins) {
        for (const int& i : coins) {
            for (int j = i; j <= amount; ++j) {
                dp[j] += dp[j - i];
            }
        }
        return dp[amount];
    }
};
    \end{lstlisting}

    \subsubsection{组合总和IV}

    \href{https://leetcode.cn/problems/combination-sum-iv/}{组合总和IV}

    数字可以重复使用，完全背包，但是本题中，不同的顺序被视为不同的答案，即【1，1，2】和【1，2，1】是两个答案，此时我们需要交换完全背包种两层for循环的顺序；

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[1005] = {1, };
public:
    int combinationSum4(vector<int>& nums, int target) {
        for (int i = 1; i <= target; ++i) {
            for (const int& j : nums) {
                if (j <= i && dp[i - j] < INT_MAX - dp[i]) {
                    dp[i] += dp[i - j];
                }
            }
        }
        return dp[target];
    }
};
    \end{lstlisting}

    先遍历物品，再遍历容量：组合数量

    先遍历容量，再遍历物品：排列数量

    如果先遍历物品的话，就相当于，物品是按照顺序依次加入的，不会出现多种排列的情况，因此计算出来的是组合的数量；

    如果后遍历物品的话，物品就有多种加入的顺序了，求解出来的就是排列的数量；

    \subsubsection{零钱兑换}

    \href{https://leetcode.cn/problems/coin-change/}{零钱兑换}

    完全背包，相当于每个硬币的重量是其面值，价值是1，背包容量是amount，求解在背包完全装满的前提下，最小的价值。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[10000 + 5];
public:
    Solution() {
        for (int& i : this->dp) i = INT_MAX;
    }

    int coinChange(vector<int>& coins, int amount) {
        dp[0] = 0;
        for (const int& i : coins) {
            for (int j = i; j <= amount; ++j) {
                if (dp[j - i] == INT_MAX) continue;
                else dp[j] = min(dp[j], dp[j - i] + 1);
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        else return dp[amount];
    }
};
    \end{lstlisting}

    \subsubsection{完全平方数}

    \href{https://leetcode.cn/problems/perfect-squares/}{完全平方数}

    类似上面的零钱兑换；

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int dp[10000 + 5];
    vector<int> squares;

    Solution() {
        for (int i = 1; i * i <= 10000; ++i) this->squares.emplace_back(i * i);
        for (int& i : this->dp) i = INT_MAX;
        dp[0] = 0;
    }

    int numSquares(int n) {
        for (int i = 0; i < squares.size() && squares[i] <= n; ++i) {
            for (int j = squares[i]; j <= n; ++j) {
                if (dp[j - squares[i]] == INT_MAX) continue;
                else dp[j] = min(dp[j], dp[j - squares[i]] + 1);
            }
        }
        return dp[n];
    }
};
    \end{lstlisting}

    \subsubsection{单词拆分}

    \href{https://leetcode.cn/problems/word-break/}{单词拆分}

    $ dp[i] $ 表示 $ s[1, i] $ 是否可以由提供的单词组成，对于 $ j < i $ ，如果 $ dp[j] = true $ 并且 $ s[j + 1, i] $ 在词典中，则可以递推出 $ dp[i] = true $ 。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    bool dp[305] = {true};
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st;
        for (const string& i: wordDict) st.insert(i);

        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && st.count(s.substr(j, i - j)) != 0) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
};
    \end{lstlisting}

    \subsubsection{打家劫舍}

    \href{https://leetcode.cn/problems/house-robber/}{打家劫舍}

    $ dp[i] $ 表示前i间房子能偷出的最大金额，如果偷了第i-1间，则第i间不能偷，$ dp[i] = dp[i - 1] $ ，如果第i-1间没偷，则可以偷第i间，$ dp[i] = dp[i - 2] + value[i] $ 。

    可以使用滚动数组优化空间。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[105] = {};
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        dp[1] = nums[0];

        for (int i = 2; i <= n; ++i) {
            int value = nums[i - 1];
            dp[i] = max(dp[i - 1], dp[i - 2] + value);
        }

        return dp[n];
    }
};
    \end{lstlisting}

    \subsubsection{打家劫舍 II}

    \href{https://leetcode.cn/problems/house-robber-ii/}{打家劫舍 II}

    这道题目，由于加上了环形的条件，第一个和最后一个不能同时打劫，所以，可以按照上一道题目的方式来偷的下标范围为 $ [1, n - 1] $ 和 $ [2, n] $ ，可以通过两次DP解决。

    滚动数组优化空间。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        int pre2 = 0, pre1 = 0, ans1, ans2;

        for (int i = 0; i < n - 1; ++i) {
            int now = max(pre1, pre2 + nums[i]);
            pre2 = pre1;
            pre1 = now;
        }

        ans1 = pre1;
        pre1 = pre2 = 0;

        for (int i = 1; i < n; ++i) {
            int now = max(pre1, pre2 + nums[i]);
            pre2 = pre1;
            pre1 = now;
        }

        ans2 = pre1;

        return max(ans1, ans2);
    }
};
    \end{lstlisting}

    \subsubsection{打家劫舍 III}

    \href{https://leetcode.cn/problems/house-robber-iii/}{打家劫舍 III}

    \textbf{树上动态规划}，一种比较暴力的记忆化搜索的解法如下：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    map<TreeNode*, int> res;  // 记忆化搜索
    int solve(TreeNode* now) {
        if (now == nullptr) return 0;
        if (!now->left && !now->right) return now->val;
        if (res.find(now) != res.end()) return res[now];

        // 抢当前节点
        int profit1 = now->val;
        if (now->left) {
            profit1 += solve(now->left->left);
            profit1 += solve(now->left->right);
        }
        if (now->right) {
            profit1 += solve(now->right->left);
            profit1 += solve(now->right->right);
        }

        // 不抢当前节点
        int profit2 = solve(now->left) + solve(now->right);

        res[now] = max(profit1, profit2);
        return max(profit1, profit2);
    }
public:
    int rob(TreeNode* root) {
        return solve(root);
    }
};
    \end{lstlisting}

    使用容器记录状态的变化，树上DP的解法：

    每个节点有两个状态，即，偷这个节点，和不偷这个节点，在这个节点对应的子树上的最大赃款。
            
    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    // first：偷当前节点，second：不偷当前节点
    pair<int, int> solve(TreeNode* now) {
        if (now == nullptr) return { 0, 0 };
        auto l_dp = solve(now->left);
        auto r_dp = solve(now->right);

        // 偷当前节点
        int profit1 = now->val + l_dp.second + r_dp.second;
        // 不偷当前节点
        int profit2 = max(l_dp.first, l_dp.second) + max(r_dp.first, r_dp.second);
        return { profit1, profit2 };
    }
public:
    int rob(TreeNode* root) {
        auto ans = solve(root);
        return max(ans.first, ans.second);
    }
};
    \end{lstlisting}

    \subsubsection{买卖股票的最佳时机}

    \href{https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/}{买卖股票的最佳时机}

    贪心做法：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = INT_MIN, low_price = prices[0];
        for (const int& i : prices) {
            low_price = min(low_price, i);
            ans = max(ans, i - low_price);
        }
        return ans;
    }
};
    \end{lstlisting}

    动态规划做法：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[100000 + 5][2] = {};
public:
    int maxProfit(vector<int>& prices) {
        dp[0][0] = -prices[0];  // 第i天持有股票的最大利润
        dp[0][1] = 0;           // 第i天不持有股票的最大利润
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.size() - 1][1];
    }
};
    \end{lstlisting}

    \subsubsection{买卖股票的最佳时机 II}

    \href{https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/}{买卖股票的最佳时机 II}

    本题中，股票可以多次买卖；

    贪心章节中，有过了贪心做法，现在讨论动态规划做法；

    dp[i][0]表示第i天，持有股票的最大利润，dp[i][0]可以由两个状态转移过来：1、第i-1天已经持有，继续保持。2、第i-1天不持有，第i天买入。即，$ d[i][0] = \max(dp[i - 1][0], dp[i - 1][1] - price[i]) $ 。

    dp[i][1]表示第i天，不持有股票的最大利润，可以由两个状态转移过来，1、第i-1天已经不持有，继续不持有。2、第i-1天持有，第i天抛出。即，$ dp[i][1] = \max(dp[i - 1][1], dp[i - 1][0] + price[i]) $ 。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[30000 + 5][2];
public:
    int maxProfit(vector<int>& prices) {
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.size() - 1][1];
    }
};
    \end{lstlisting}

    \subsubsection{买卖股票的最佳时机 III}

    \href{https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/}{买卖股票的最佳时机 III}

    本题中，股票只可以买卖两次；

    \paragraph{确定DP数组的下标，及其含义}~{}

    因为可以买卖两次，所以，一共有四种状态：

    \begin{enumerate}
        \item 第一次持有股票
        \item 第一次不持有股票
        \item 第二次持有股票
        \item 第二次不持有股票
    \end{enumerate}

    \paragraph{确定递推公式}~{}

    \begin{enumerate}
        \item $ dp[i][1] = \max(dp[i - 1][1], -price[i]) $
        \item $ dp[i][2] = \max(dp[i - 1][2], dp[i - 1][1] + price[i]) $
        \item $ dp[i][3] = \max(dp[i - 1][3], dp[i - 1][2] - price[i]) $
        \item $ dp[i][4] = \max(dp[i - 1][4], dp[i - 1][3] + price[i]) $
    \end{enumerate}

    \paragraph{初始化DP数组}~{}

    \begin{enumerate}
        \item $ dp[0][1] = -price[0] $
        \item $ dp[0][2] = 0 $
        \item $ dp[0][3] = -price[0] $
        \item $ dp[0][4] = 0 $
    \end{enumerate}

    \paragraph{确定DP的顺序}~{}

    从前往后，线性遍历。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    // 0 第一次持有股票
    // 1 第一次未持有股票
    // 2 第二次持有股票
    // 3 第二次未持有股票
    int dp[100000 + 5][4] = {};
public:
    int maxProfit(vector<int>& prices) {
        dp[0][0] = -prices[0];
        dp[0][2] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
        }
        return dp[prices.size() - 1][3];
    }
};
    \end{lstlisting}

    优化空间后的结果如下：

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};
    \end{lstlisting}

    \subsubsection{买卖股票的最佳时机 IV}

    \href{https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/}{买卖股票的最佳时机 IV}

    最多可以完成k笔交易，求解最大利润。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[1000 + 5][200 + 5] = {};
public:
    int maxProfit(int k, vector<int>& prices) {
        for (int j = 1; j <= 2 * k; j += 2) dp[0][j] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            for (int j = 1; j <= 2 * k; j += 2) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
            for (int j = 2; j <= 2 * k; j += 2) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
        }
        return dp[prices.size() - 1][2 * k];
    }
};
    \end{lstlisting}

    \subsubsection{买卖股票的最佳时机，含冷冻期}

    \href{https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/}{买卖股票的最佳时机，含冷冻期}

    股票可以交易任意次，但是抛售股票之后，需要有一天的冷冻期，才能重新买入。

    确定本题中动态规划的状态如下：

    \begin{enumerate}
        \item 持有股票的状态；$ dp[i][1] = \max(dp[i - 1][1], dp[i - 1][2] - price[i], dp[i - 1][4] - price[i]) $
        \item 保持卖出股票的状态；$ dp[i][2] = \max(dp[i - 1][2], dp[i - 1][4]) $
        \item 当天卖出股票；$ dp[i][3] = dp[i - 1][1] + prices[i] $
        \item 今天为冷冻期；$ dp[i][4] = dp[i - 1][3] $
    \end{enumerate}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
    // 0 持有状态
    // 1 保持卖出状态
    // 2 今天卖出
    // 3 今天冷冻期
    int dp[5000 + 5][4] = {};
public:
    int maxProfit(vector<int>& prices) {
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][3]) - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return max(dp[prices.size() - 1][1], max(dp[prices.size() - 1][2], dp[prices.size() - 1][3]));
    }
};
    \end{lstlisting}

    \subsubsection{最长上升子序列}

    \href{https://leetcode.cn/problems/longest-increasing-subsequence/}{最长上升子序列}

    Longest Increasing Subsequence，LIS。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[2555] = {};
public:
    int lengthOfLIS(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{最长连续递增序列}

    \href{https://leetcode.cn/problems/longest-continuous-increasing-subsequence/}{最长连续递增序列}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// 贪心
class Solution1 {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 1, res = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i - 1]) {
                ++res;
                ans = max(ans, res);
            } else {
                res = 1;
            }
        }
        return ans;
    }
};

// 动态规划
class Solution {
private:
    int dp[10000 + 5];
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 1;
        for (int i = 0; i < nums.size(); ++i) dp[i] = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i - 1] < nums[i]) dp[i] = dp[i - 1] + 1;
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{最长重复子数组}

    \href{https://leetcode.cn/problems/maximum-length-of-repeated-subarray/}{最长重复子数组}

    dp[i][j]表示1中以i结尾的子数组，与2中以j结尾的子数组，相等的最大长度，当nums[i] == nums[j]时，dp[i][j] = dp[i - 1][j - 1] + 1。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[1005][1005] = {};
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        for (int i = 0; i < nums1.size(); ++i) {
            for (int j = 0; j < nums2.size(); ++j) {
                if (nums1[i] == nums2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    ans = max(ans, dp[i + 1][j + 1]);
                }
            }
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{最长公共子序列}

    \href{https://leetcode.cn/problems/longest-common-subsequence/}{最长公共子序列}

    dp[i][j]表示串1的[1, i]与串2的[1, j]的最长公共子序列长度，当s1[i] == s2[j]时，dp[i][j] = dp[i - 1][j - 1] + 1，当s1[i] != s2[j]时，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
    int dp[1005][1005] = {};
public:
    int longestCommonSubsequence(string text1, string text2) {
        const int n = text1.size(), m = text2.size();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
};
    \end{lstlisting}

    \subsubsection{不相交的线}

    \href{https://leetcode.cn/problems/uncrossed-lines/}{不相交的线}

    与上一道题目雷同。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[505][505] = {};
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        const int n = nums1.size(), m = nums2.size();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
};
    \end{lstlisting}

    \subsubsection{最大子数组和}

    \href{https://leetcode.cn/problems/maximum-subarray/}{最大子数组和}

    水题。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution1 {  // 动态规划
private:
    int dp[100000 + 5];
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

class Solution2 { // 贪心，其实不太严谨
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int now = 0;
        for (int i : nums) {
            if (now > 0) now += i; 
            else now = i;
            ans = max(ans, now);
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{判断子序列}

    \href{https://leetcode.cn/problems/is-subsequence/}{判断子序列}

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution1 { // 动态规划做法，dp[i][j]表示t[1, i]与s[1, j]的最长子序列长度
private:
    int dp[10000 + 5][100 + 5] = {};
public:
    bool isSubsequence(string s, string t) {
        if (s.empty()) return true;
        const int n = t.size(), m = s.size();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (t[i - 1] == s[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
            if (dp[i][m] == m) return true;
        }
        return false;
    }
};

class Solution2 { // 双指针做法
public:
    bool isSubsequence(string s, string t) {
        int idx = 0;
        for (int i = 0; i < t.size() && idx < s.size(); ++i)
            if (t[i] == s[idx]) ++idx;
        return idx == s.size();
    }
};
    \end{lstlisting}

    \subsubsection{不同的子序列}

    \href{https://leetcode.cn/problems/distinct-subsequences/}{不同的子序列}

    dp[i][j]定义为，s[1, i]的所有子序列中，等于t[1, j]的子序列的个数。

    当s[i] == t[j]时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，都向后扩展一位或者s向后扩展一位。

    当s[i] != t[j]时，dp[i][j] = dp[i - 1][j]。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    unsigned long long dp[1005][1005] = {};
public:
    int numDistinct(string s, string t) {
        if (s.size() < t.size()) return 0;
        const int n = s.size(), m = t.size();

        for (int i = 1; i <= n; ++i) {
            dp[i - 1][0] = 1;
            for (int j = 1; j <= m; ++j) {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][m];
    }
};
    \end{lstlisting}

    \subsubsection{两个字符串的删除操作}

    \href{https://leetcode.cn/problems/delete-operation-for-two-strings/}{两个字符串的删除操作}

    公共子序列长度裸题；

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[505][505] = {};
public:
    int minDistance(string word1, string word2) {
        const int n = word1.size(), m = word2.size();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return n + m - 2 * dp[n][m];
    }
};
    \end{lstlisting}

    \subsubsection{编辑距离}

    \href{https://leetcode.cn/problems/edit-distance/}{编辑距离}

    dp[i][j]表示s1[1, i]与s2[1, j]的最小编辑距离。

    如果s1[i] == s2[j]，则dp[i][j] = dp[i - 1][j - 1]。

    如果s1[i] != s2[j]，要进行删除或者添加的话，dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1，如果进行替换的话，dp[i][j] = dp[i - 1][j - 1] + 1。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[505][505] = {};
public:
    int minDistance(string word1, string word2) {
        const int n = word1.size(), m = word2.size();
        for (int i = 1; i <= n; ++i) dp[i][0] = i;
        for (int j = 1; j <= m; ++j) dp[0][j] = j;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
        return dp[n][m];
    }
};
    \end{lstlisting}

    \subsubsection{回文子串}

    \href{https://leetcode.cn/problems/palindromic-substrings/}{回文子串}

    dp[i][j]表示s[i, j]是否为一个回文子串；

    如果s[i] == s[j]，当j - i <= 1时，dp[i][j]一定等于true，否则，检查dp[i + 1][j - 1]的状态；

    因为递推公式，所以遍历时，需要i从大到小，j从小到大（dp[i][j]依赖dp[i + 1][j - 1]）。

    此外，本题还可以有 $ \Theta(n^2) $ 的双指针做法。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    bool dp[1005][1005];
public:
    int countSubstrings(string s) {
        int ans = 0;
        const int n = s.size();
        for (int i = n; i >= 1; --i) {
            for (int j = i; j <= n; ++j) {
                if (s[i - 1] == s[j - 1]) {
                    if (j - i <= 1) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{最长回文子序列}

    \href{https://leetcode.cn/problems/longest-palindromic-subsequence/}{最长回文子序列}

    dp[i][j]表示s[i, j]中的最长回文子串，状态转移，当s[i] == s[j]时，dp[i][j] = sp[i + 1][j - 1] + 2，否则，dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。

    初始状态dp[i][i] = 1，遍历顺序，i从大到小，j从小到大。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp[1005][1005] = {};
public:
    int longestPalindromeSubseq(string s) {
        const int n = s.size();

        for (int i = n; i >= 1; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j <= n; ++j) {
                if (s[i - 1] == s[j - 1]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[1][n];
    }
};
    \end{lstlisting}

    \subsection{单调栈}

    \subsubsection{每日温度}

    \href{https://leetcode.cn/problems/daily-temperatures/}{每日温度}

    根据题目需要，需要从后往前遍历。这里使用一个双端队列作为单调栈，队列中的元素，从队首到队尾，温度递减。

    对于当前温度，如果队首的元素温度低于当前，则队首不是答案，弹出队首，直到队首的元素大于当前温度，获得当前答案。

    之后，将当前元素添加到队首，开始遍历下一个元素。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        const int n = temperatures.size();
        vector<int> ans(n, 0);
        deque<pair<int, int>> q;
        q.emplace_back(temperatures.back(), n - 1);

        for (int i = n - 2; i >= 0; --i) {
            while (!q.empty() && q.front().first <= temperatures[i]) q.pop_front();
            if (!q.empty()) {
                ans[i] = q.front().second - i;
            }
            q.emplace_front(temperatures[i], i);
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{下一个更大元素 I}

    \href{https://leetcode.cn/problems/next-greater-element-i/}{下一个更大元素 I}

    非常裸的单调栈。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        const int n = nums1.size(), m = nums2.size();
        unordered_map<int, int> mp;
        vector<int> ans(n, -1);
        deque<int> q;

        for (int i = m - 1; i >= 0; --i) {
            while (!q.empty() && nums2[i] >= nums2[q.front()]) q.pop_front();
            if (!q.empty()) mp[nums2[i]] = nums2[q.front()];
            q.emplace_front(i);
        }

        for (int i = 0; i < n; ++i)
            if (mp.find(nums1[i]) != mp.end())
                ans[i] = mp[nums1[i]];
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{下一个更大元素 II}

    \href{https://leetcode.cn/problems/next-greater-element-ii/}{下一个更大元素 II}

    本题中是循环数组（首尾相连）求下一个更大元素，遍历两遍即可。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(n, -1);
        deque<int> q;

        for (int i = n - 1; i >= 0; --i) {
            while (!q.empty() && nums[q.front()] <= nums[i]) q.pop_front();
            if (!q.empty()) ans[i] = nums[q.front()];
            q.push_front(i);
        }

        for (int i = n - 1; i >= 0; --i) {
            while (!q.empty() && nums[q.front()] <= nums[i]) q.pop_front();
            if (!q.empty()) ans[i] = nums[q.front()];
            q.push_front(i);
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{接雨水}

    \href{https://leetcode.cn/problems/trapping-rain-water/}{接雨水}

    首先是动态规划做法，dp\_l[i]表示i以及i左侧的最大值，dp\_r[i]表示i以及i右边的最大值，则，i处能接住的雨水量为 $ \min(dp\_l[i], dp\_r[i]) - height[i] $ 。

    两个dp数组可以很轻易的求出。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
private:
    int dp_l[20000 + 5] = {}, dp_r[20000 + 5] = {};
public:
    int trap(vector<int>& height) {
        const int n = height.size();

        dp_l[0] = height[0];
        for (int i = 1; i < n; ++i) dp_l[i] = max(dp_l[i - 1], height[i]);

        dp_r[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) dp_r[i] = max(dp_r[i + 1], height[i]);

        int ans = 0;
        for (int i = 0; i < n; ++i) ans += min(dp_l[i], dp_r[i]) - height[i];
        return ans;
    }
};
    \end{lstlisting}

    单调栈做法，双端队列实现，队列储存下标，队首到队尾，下标对应的高度递增，根据代码理解。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int trap(vector<int>& height) {
        const int n = height.size();

        int ans = 0;
        deque<int> q;
        for (int i = 0; i < n; ++i) {
            while (!q.empty() && height[q.front()] < height[i]) {
                int mid = q.front(); q.pop_front();
                if (q.empty()) break;  // 如果没有下一个元素的话，是存不下水的
                int left = q.front();

                int h = min(height[left], height[i]) - height[mid];
                int w = i - left - 1;
                ans += h * w;
            }
            q.push_front(i);
        }
        return ans;
    }
};
    \end{lstlisting}

    \subsubsection{柱状图的最大矩形}

    \href{https://leetcode.cn/problems/largest-rectangle-in-histogram/}{柱状图的最大矩形}

    对于某一个柱子，找到它两侧第一个比他矮的柱子，就获得了一个矩形。

    单调栈中，从头到尾，高度递减。

    \begin{lstlisting}[language=C++, lineskip=3pt]
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), 0);
        heights.emplace_back(0);

        int ans = 0;
        const int n = heights.size();
        deque<int> q;
        q.emplace_back(0);

        for (int i = 1; i < n; ++i) {
            while (heights[i] < heights[q.front()]) {
                int mid = q.front(); q.pop_front();
                int left = q.front();

                int w = i - left - 1;
                int h = heights[mid];
                ans = max(ans, h * w);
            }
            q.push_front(i);
        }

        return ans;
    }
};
    \end{lstlisting}

    \subsection{一些其他题目}

    2023年3月1日，21点14分

    \subsubsection{轮转数组}

    \href{https://leetcode.cn/problems/rotate-array/}{轮转数组}

    \begin{lstlisting}[language=C++, lineskip=3pt]
// Template
    \end{lstlisting}

    \subsection{其他知识点}

    为什么需要内存对齐？一是为了跨平台，而是为了增加处理器访问内存的效率。

    \begin{lstlisting}[language=C++, lineskip=3pt]
// Template
    \end{lstlisting}

    \clearpage
    \section{算法二刷·李煜东 \& ACMer时代留下的笔记}

    参考资料，书籍，《算法竞赛进阶指南》\cite{li_yu_dong}。

    \clearpage
    \section{复习C++}

    参考资料，书籍，《C++ Primer Plus》\cite{cpp_primer_plus}。

    \subsection{杂项知识点整理}

    \subsubsection{为什么构造函数和析构函数中，不建议抛出异常}

    对于析构函数，抛出异常后，异常点后面的代码都不会被执行，如果异常点后面的代码有释放资源的操作，则这些操作就不会被执行，造成资源、内存的泄漏。

    \textbf{因此，十分不建议在析构函数中，抛出异常！！！}

    对于构造函数，如果构造函数中抛出了异常，则认为对象没有构造成功，也就不会调用这个对象的析构函数，因此，一些已经初始化了的、需要在析构函数中释放的资源就不会被释放，但是成员变量会被释放。

    \subsubsection{关于类中static成员变量的初始化}

    如果是，static，并且const的成员变量，只需要在内类进行声明和初始化，就可以正常被读取。

    如果是，static，但是不const的成员变量，除了要在类内声明以外，还要在类外进行声明，才能被正常访问。

    如果一个static的成员变量，想要直接在类内初始化，则必须是const的。

    如下代码编译正常：

    \begin{lstlisting}[language=C++, lineskip=3pt]
#include <bits/stdc++.h>
using namespace std;

class Test {
public:
    static const int data = 1;
};

int main() {
    cout << Test::data << endl;
}
    \end{lstlisting}

    如下代码编译不通过：

    \begin{lstlisting}[language=C++, lineskip=3pt]
#include <bits/stdc++.h>
using namespace std;

class Test {
public:
    static int data;
};

int main() {
    cout << Test::data << endl;
}

/*
CMakeFiles\Accepted.dir/objects.a(main.cpp.obj):main.cpp:(.rdata$.refptr._ZN4Test4dataE[.refptr._ZN4Test4dataE]+0x0): undefined reference to `Test::data'
collect2.exe: error: ld returned 1 exit status
mingw32-make.exe[3]: *** [CMakeFiles\Accepted.dir\build.make:98: Accepted.exe] Error 1
mingw32-make.exe[2]: *** [CMakeFiles\Makefile2:82: CMakeFiles/Accepted.dir/all] Error 2
mingw32-make.exe[1]: *** [CMakeFiles\Makefile2:89: CMakeFiles/Accepted.dir/rule] Error 2
mingw32-make.exe: *** [Makefile:123: Accepted] Error 2
*/
    \end{lstlisting}

    如下代码可以通过编译，正常运行：

    \begin{lstlisting}[language=C++, lineskip=3pt]
#include <bits/stdc++.h>
using namespace std;

class Test {
public:
    static int data;
};

int Test::data = 1;

int main() {
    cout << Test::data << endl;
}
    \end{lstlisting}

    \clearpage
    \section{C++零碎}

    \subsection{在priority\_queue中，使用Lambda表达式自定义比较函数}

    \begin{lstlisting}[language=C++, lineskip=3pt]
auto cmp = [](pair<int, int> a, pair<int, int>b) -> bool {
    return a.first > b.first;
};

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
    \end{lstlisting}

    \subsection{lower\_bound和upper\_bound}

    Lower Bound和Upper Bound都是C++ STL提供的二分查找，输入应为单调递增的序列。

    Lower Bound函数在闭区间 $ [begin, end - 1] $ 中寻找第一个 $ \ge x $ 的数字，如果没有，则返回 $ end $ 。

    Upper Bound函数在闭区间 $ [begin, end - 1] $ 中寻找第一个 $ > x $ 的数字，如果没有，则返回 $ end $ 。

    \begin{lstlisting}[language=C++, lineskip=3pt]
int main() {
    int arr[] = { 1, 2, 3, 4, 5 };
    cout << lower_bound(arr, arr + 5, 3) - arr + 1 << endl;
    cout << upper_bound(arr, arr + 5, 3) - arr + 1 << endl;
    cout << endl;
    cout << lower_bound(arr, arr + 5, 233) - arr + 1 << endl;
    cout << upper_bound(arr, arr + 5, 233) - arr + 1 << endl;
//    Output:
//    3
//    4
//
//    6
//    6
}
    \end{lstlisting}

    \clearpage
    \section{MySQL刷题，牛客，Leetcode}

    \subsection{牛客网的SQL}

    having和where的区别：having在group by之后，对数据进行过滤，where在group by之前，对数据进行过滤。having后面可以使用聚合函数，where后面不可以使用聚合函数。

    SQL中的like模糊查询：百分号\%可以匹配0个或者任意多个字符；下划线\_可以匹配任意单个字符；中括号[]可以匹配指定范围或者指定集合中的单个字符，例如[abcd]或者[a-z]，[\^]匹配不属于集合或者范围内的单个字符；*和?的含义与命令行中相同；\#代表单个数字。

    \subsubsection{SQL21 浙江大学用户题目回答情况}

    \href{https://www.nowcoder.com/practice/55f3d94c3f4d47b69833b335867c06c1?tpId=199&tqId=1975671&ru=%2Fpractice%2F009d8067d2df47fea429afe2e7b9de45&qru=%2Fta%2Fsql-quick-study%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D199}{链接}，考察子查询，也可以用内连接来做。

    两张表进行内连接的做法:

    \begin{lstlisting}[language=SQL, lineskip=3pt]
        select 
            user_profile.device_id,
            question_practice_detail.question_id,
            question_practice_detail.result
        from
            user_profile inner join question_practice_detail
            on user_profile.device_id = question_practice_detail.device_id and user_profile.university = "浙江大学"
        order by
            question_practice_detail.question_id;
    \end{lstlisting}

    使用子查询的做法：

    \begin{lstlisting}[language=SQL, lineskip=3pt]
        select 
            device_id, 
            question_id, 
            result
        from 
            question_practice_detail
        where 
            device_id in (
                select 
                    device_id
                from 
                    user_profile
                where
                    university = "浙江大学"
            )
        order by
            question_id;
    \end{lstlisting}

    \clearpage
    \bibliography{References}
    \bibliographystyle{unsrt}
    
\end{document}
